Question

A unit disk graph is an intersection graph $G = (V,E)$, such that given $n$ disks on the plane with identical radius. Each disk $d_u$ corresponds to a vertex $u \in V$, and there is an edge $uv \in E$ if, and only if $d_u$ and $d_v$ intersects.

In 1990, Clark, Colbourn, and Johnson showed that the problem can be solved in polynomial time. However, the linked paper does not provide an exact algorithm.

I have been studying the paper for some time, and I still don't see how the observations in Section 3 can be utilized to develop an algorithm. Mostly because point sets that are used to prove the claims are infinite.

Moreover, I have scanned through many papers, and all of them mention the polynomial-time solvability only. I could not even find a verbal definition of the algorithm anywhere.

I am not asking for coding or some well-defined algorithm, but I would really appreciate a roughly written complete algorithm.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top