2026-07-21T14:13:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23215 2025-10-02T12:43:17Z ddc:004 open_access

The Maximum Clique Problem in a Disk Graph Made Easy Keil, J. Mark Mondal, Debajyoti Geometric Intersection Graphs Disk Graphs Ball Graphs Maximum Clique A disk graph is an intersection graph of disks in ℝ². 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. In this paper, we provide a new perspective to examine adjacencies in a disk graph that helps obtain the following results. - We design an 𝒪^*(n^{2k})-time algorithm, where 𝒪^* hides a polynomial factor, 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 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 𝒪^*(n^{2rk})-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. - We design an 𝒪^*(n^{2k})-time algorithm to find a maximum clique in the intersection graph of a set S of n L-visible convex polygons, where k is the number of distinct shapes in S. This contrasts the known hardness result on finding a maximum clique in the intersection graph of unit disks and axis-aligned rectangles. Schloss Dagstuhl – Leibniz-Zentrum für Informatik J. Mark Keil and Debajyoti Mondal 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.63 urn:nbn:de:0030-drops-232155 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.63 eng https://creativecommons.org/licenses/by/4.0/legalcode