2022/09/05 by Dibyayan Chakraborty, Kshitij Gajjar, Chakraborty, Dibyayan +3 · 1 citation
Computer Science · #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2209.01851
openalex publication_date 2022/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we determine the computational complexity of recognizing two graph classes, grounded L-graphs and stabbable grid intersection graphs. An L-shape is made by joining the bottom end-point of a vertical (\vert) segment to the left end-point of a horizontal (-) segment. The top end-point of the vertical segment is known as the \em anchor of the L-shape. Grounded L-graphs are the intersection graphs of L-shapes such that all the L-shapes' anchors lie on the same horizontal line. We show that recognizing grounded L-graphs is NP-complete. This answers an open question asked by Jel'ınek & Töpfer (Electron. J. Comb., 2019). Grid intersection graphs are the intersection graphs of axis-parallel line segments in which two vertical (similarly, two horizontal) segments cannot intersect. We say that a (not necessarily axis-parallel) straight line ℓ stabs a segment s, if s intersects ℓ. A graph G is a stabbable grid intersection graph (StabGIG) if there is a grid intersection representation of G in which the same line stabs all its segments. We show that recognizing StabGIG graphs is NP-complete, even on a restricted class of graphs. This answers an open question asked by Chaplick \etal (Order, 2018).