2021/04/20 by Dibyayan Chakraborty, Kshitij Gajjar, Chakraborty, Dibyayan +1 · 1 citation
Computer Science · Engineering · Environmental Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Manufacturing Process and Optimization #Remote Sensing and LiDAR Applications
paper · pdf · doi:10.48550/arxiv.2104.09976
openalex publication_date 2021/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Planar graphs can be represented as intersection graphs of different types of geometric objects in the plane, e.g., circles (Koebe, 1936), line segments (Chalopin & Gonçalves, 2009), L-shapes (Gonçalves et al, 2018). For general graphs, however, even deciding whether such representations exist is often NP-hard. We consider apex graphs, i.e., graphs that can be made planar by removing one vertex from them. We show, somewhat surprisingly, that deciding whether geometric representations exist for apex graphs is NP-hard. More precisely, we show that for every positive integer k, recognizing every graph class G which satisfies PURE-2-DIR ⊆ G ⊆ 1-STRING is NP-hard, even when the input graphs are apex graphs of girth at least k. Here, PURE-2-DIR is the class of intersection graphs of axis-parallel line segments (where intersections are allowed only between horizontal and vertical segments) and 1-STRING is the class of intersection graphs of simple curves (where two curves share at most one point) in the plane. This partially answers an open question raised by Kratochv'ıl & Pergel (2007). Most known NP-hardness reductions for these problems are from variants of 3-SAT. We reduce from the PLANAR HAMILTONIAN PATH COMPLETION problem, which uses the more intuitive notion of planarity. As a result, our proof is much simpler and encapsulates several classes of geometric graphs.