2025/12/20 by J. Mark Keil, Keil, J. Mark, Debajyoti Mondal +1
Computer Science · #52C99 #68Q25 #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #I.3.5 #Topological and Geometric Data Analysis
paper · doi:10.48550/arxiv.2512.18223
openalex publication_date 2025/12/20 · openalex created_date 2025/12/24 · openalex updated_date 2026/07/28
A geometric intersection graph is constructed over a set of geometric objects, where each vertex represents a distinct object and an edge connects two vertices if and only if the corresponding objects intersect. We examine the problem of finding a maximum clique in the intersection graphs of segments and disks under grounded and stabbed constraints. In the grounded setting, all objects lie above a common horizontal line and touch that line. In the stabbed setting, all objects can be stabbed with a common line. - We prove that finding a maximum clique is NP-hard for the intersection graphs of upward rays. This strengthens the previously known NP-hardness for ray graphs and settles the open question for the grounded segment graphs. The hardness result holds in the stabbed setting. - We show that the problem is polynomial-time solvable for intersection graphs of grounded unit-length segments, but NP-hard for stabbed unit-length segments. - We give a polynomial-time algorithm for the case of grounded disks. If the grounded constraint is relaxed, then we give an O(n3 f(n))-time 3/2-approximation for disk intersection graphs with radii in the interval [1,3], where n is the number of disks and f(n) is the time to compute a maximum clique in an n-vertex cobipartite graph. This is faster than previously known randomized EPTAS, QPTAS, or 2-approximation algorithms for arbitrary disks. We obtain our result by proving that pairwise intersecting disks with radii in [1,3] are 3-pierceable, which extends the 3-pierceable property from the long known unit disk case to a broader class.