Recognizing geometric intersection graphs stabbed by a line

DOI10.1016/J.TCS.2024.114488MaRDI QIDQ6204544OpenAlexFDO

Authors Dibyayan Chakraborty, Kshitij Gajjar, Irena Rusu

Publication date 28 March 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.01851

zbMATH Keywords

complexityNP-completenessintersection graphgrounded L-graphstabbable grid intersection graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: In this paper, we determine the computational complexity of recognizing two graph classes, emph{grounded L}-graphs and emph{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{'i}nek & T{"o}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 $ell$ stabs a segment $s$, if $s$ intersects $ell$. 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 ( extsc{O}rder, 2018).

Recommendations

• On rectangle intersection graphs with stab number at most two
• Intersection graphs of rays and grounded segments
• Intersection graphs of rays and grounded segments
• Edge intersection graphs of \(L\)-shaped paths in grids
• On unit grid intersection graphs and several other intersection graph classes

Cites work

• scientific article; zbMATH DE number 6850320 (Why is no real title available?)
• A special planar satisfiability problem and a consequence of its NP- completeness
• Characterizations of deque and queue graphs
• Computing maximum independent set on outerstring graphs and their relatives
• Covering and coloring problems for relatives of intervals
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Fast and accurate algorithms for protein side-chain packing
• Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems
• Finding geometric representations of apex graphs is NP-hard
• Grid intersection graphs and order dimension
• Label placement by maximum independent set in rectangles
• On a Coloring Problem.
• On bounding the chromatic number of L-graphs
• On dominating set of some subclasses of string graphs
• On grid intersection graphs
• On grounded \(\llcorner\)-graphs and their relatives
• On the complexity of recognizing Stick, BipHook and max point-tolerance graphs
• Rectangle and Square Representations of Planar Graphs
• Representation of a finite graph by a set of intervals on the real line
• The book thickness of a graph
• Vertex Intersection Graphs of Paths on a Grid

This page was built for publication: Recognizing geometric intersection graphs stabbed by a line

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6204544)