Example: Cliques in unit-disk graphs

Every generalized octhedron Ot is a unit-disk graph. Nevertheless it turns out that a maximum clique can be found in polynomial time provided we have the model available. This is a nice example where reconstruction could be motivated by some optimization problem. Unfortunately, unit-disk graphs cannot be reconstructed efficiently---the recognition problem for unit-disk graphs is NP-hard [BK98]. Thus the complexity status of the maximum clique problem restricted to unit-disk graphs (without a representation given) is still open.

[CCJ90]: There is some O(n4.5)-time algorithm to find a maximum clique in a unit-disk graph provided the model is given.

Proof: First we provide a fresh view on the model. Let G=(V,E) be the intersection graph of the family (Sx/x V) of unit-disks in the plane. Let px be the center of Sx. Obviously Sx and Sy intersect iff the distance between px and py is at most 2. Therefore it suffices to look at these points px.

For xy E, let Axy denote the set of all z V for which pz is contained in both (closed) circles around px and py with radius d(pxpy). Certainly each such z (different from x,y) must be adjacent to both x and y in G. These sets Axy are not complete, but they induce complements of bipartite graphs. This can be seen by drawing the line between px and py. Each half has diameter less than 2, therefore vertices corresponding to points in each half are pairwise adjacent.

Maximum cliques in complements of bipartite graphs, i.e. maximum independent sets in bipartite graphs, can be found in time O(n2.5) via maximum matching in bipartite graphs.

Any clique C of G is contained in Axy where we choose x,y V(C) with maximum distance. Thus by finding maximum cliques in each of the n2 graphs Axy, we find a maximum clique of G.

What about the MAXCLIQUE problem for unit-disk graphs without a representation given? Can a maximum clique at least be approximated then?

Back to the start page for intersection graphs?

Erich Prisner
made on January 12, 1999