Abstract
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 longstanding open question that has been very well studied in the literature. The problem is known to be open even when the radii of all the disks are in the interval [1,(1+ε)], where ε > 0. If all the disks are unit disks then there exists an O(n³log n)time algorithm to compute a maximum clique, which is the bestknown running time for over a decade. Although the problem of computing a maximum clique in a disk graph remains open, it is known to be APXhard for the intersection graphs of many other convex objects such as intersection graphs of ellipses, triangles, and a combination of unit disks and axisparallel rectangles. Here we obtain the following results.
 We give an algorithm to compute a maximum clique in a unit disk graph in O(n^2.5 log n)time, which improves the previously best known running time of O(n³log n) [Eppstein '09].
 We extend a widely used "co2subdivision approach" to prove that computing a maximum clique in a combination of unit disks and axisparallel rectangles is NPhard to approximate within 4448/4449 ≈ 0.9997. The use of a "co2subdivision approach" was previously thought to be unlikely in this setting [Bonnet et al. '20]. Our result improves the previously known inapproximability factor of 7633010347/7633010348 ≈ 0.9999.
 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+ε)]. For example, if the minimum lens width is at least 0.265 and ε ≤ 0.0001, which still allows for nonHelly triples in the arrangement, then one can find a maximum clique in polynomial time.
BibTeX  Entry
@InProceedings{espenant_et_al:LIPIcs.SoCG.2023.30,
author = {Espenant, Jared and Keil, J. Mark and Mondal, Debajyoti},
title = {{Finding a Maximum Clique in a Disk Graph}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {30:130:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772730},
ISSN = {18688969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17880},
URN = {urn:nbn:de:0030drops178803},
doi = {10.4230/LIPIcs.SoCG.2023.30},
annote = {Keywords: Maximum clique, Disk graph, Time complexity, APXhardness}
}
Keywords: 

Maximum clique, Disk graph, Time complexity, APXhardness 
Collection: 

39th International Symposium on Computational Geometry (SoCG 2023) 
Issue Date: 

2023 
Date of publication: 

09.06.2023 