A disk graph is an intersection graph of disks in the Euclidean plane, where the disks correspond to the vertices of the graph and a pair of vertices are adjacent if and only if their corresponding disks intersect. The problem of determining the time complexity of computing a maximum clique in a disk graph is a long-standing open question that has been very well studied in the literature. In this paper, we obtain the following results. We first give an algorithm to compute a maximum clique in a unit disk graph in \(O(n^{7/3+o(1)})\) -time, which improves the previously best-known running time of \(O(n^3\log n)\) . We next extend a widely used ‘co-2-subdivision approach’ to prove that computing a maximum clique in a combination of unit disks and axis-parallel rectangles is NP-hard to approximate within 0.9997. The use of a ‘co-2-subdivision approach’ was previously thought to be unlikely in this setting. Our result improves the previously known inapproximability factor of 0.9999. Finally, we show that the parameter minimum lens width of the disk arrangement may be used to make progress in the case when disk radii are in \([1,1+\varepsilon ]\) . For example, if the minimum lens width is at least 0.265 and \( \varepsilon \le 0.0001\) , then one can find a maximum clique in polynomial time.
