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^2k 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⁵ n) -time. This is at least a factor of n^4/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^2rk 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.