The Maximum Clique Problem in a Disk Graph Made Easy

A disk graph is an intersection graph of disks in R². Determining the computational complexity of finding a maximum clique in a disk graph is a long-standing open problem. In 1990, Clark, Colbourn, and Johnson gave a polynomial-time algorithm for computing a maximum clique in a unit disk graph. However, finding a maximum clique when disks are of arbitrary size is widely believed to be a challenging open problem. The problem is open even if we restrict the disks to have at most two different sizes of radii, or restrict the radii to be within [1,1+ε] for some ε>0. In this paper, we provide a new perspective to examine adjacencies in a disk graph that helps obtain the following results. - We design an O(2ᵏ n²ᵏ poly(n))-time algorithm to find a maximum clique in a n-vertex disk graph with k different sizes of radii. This is polynomial for every fixed k, and thus settles the open question for the case when $k=2$. - Given a set of n unit disks, we show how to compute a maximum clique inside each possible axis-aligned rectangle determined by the disk centers in O(n⁵log n)-time. This is at least a factor of n4/3 faster than applying the fastest known algorithm for finding a maximum clique in a unit disk graph for each rectangle independently. - We give an O(2ᵏn²ʳᵏ poly(n,r))-time algorithm to find a maximum clique in a n-vertex ball graph with k different sizes of radii where the ball centers lie on r parallel planes. This is polynomial for every fixed k and r, and thus contrasts the previously known NP-hardness result for finding a maximum clique in an arbitrary ball graph.