QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for $\text{textsc}MaximumClique$ on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show the rather surprising structural result that a disjoint union of cycles is the complement of a disk graph if and only if at most one of those cycles is of odd length. From that, we derive the first QPTAS and subexponential algorithm running in time $2^{\tilde{O}(n^{2\mathrm{/}3})}$ for $\text{textsc}MaximumClique$ on disk graphs. In stark contrast, $\text{textsc}MaximumClique$ on intersection graphs of filled ellipses or filled triangles is unlikely to have such algorithms, even when the ellipses are close to unit disks. Indeed, we show that there is a constant approximation which is not attainable even in time $2^{n^{1-\epsilon }}$, unless the Exponential Time Hypothesis fails.