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.


1 Answer 1


First note that the algorithm is expressed in the so-called proximity model (see preliminaries), so in what follows the points considered will be the centers of your circles, and $d$ will be their common diameter.

It may be confusing, as the circles drawn in the observations are not directly related to the circles from the intersection model (the radius is $d(a,b)$).

With the notations of the article, $H_{A,B}$ is finite because $V$ itself is finite ($H_{A,B}$ is a subset of the $n$ input points).

Input: d, G = (V, E) with V set of points in the plane, and E is the set
       of {u, v} s.t. d(u, v) <= d
best clique = empty
for all pair of points (u, v) from V:
    let V' = set of vertices w of V s.t. d(u, w) <= d and d(v, w) <= d
    let E' = set of {x, y} s.t. x and y are in V' and d(x, y) > d
    // G' = (V', E') is bipartite
    candidate clique = MaxIndependentSet(G')
    best clique = max(best clique, candidate clique)
return best clique

If you want to use Hopcroft-Karp, you may need to have an explicit partition $V'=A\cup B$ s.t. all edges of $E'$ are connecting a vertex of $A$ and a vertex of $B$. This can be done by checking the sign of the cross product $(\textbf{w}-\textbf{u})\times(\textbf{v}-\textbf{u})$.

  • $\begingroup$ Now I see. The points mentioned are the centers of the disks! I misunderstood the claim. Thank you very much! $\endgroup$
    – padawan
    Dec 4, 2017 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.