# What is the exact algorithm to find maximum clique of a given unit disk graph?

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.

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})$.

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