Recognizing Geometric Intersection Graphs Stabbed by a Line

In this paper, we determine the computational complexity of recognizing two graph classes, grounded \textsc{L}-graphs and stabbable grid intersection graphs. An \textsc{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 \textsc{L}-shape. Grounded \textsc{L}-graphs are the intersection graphs of \textsc{L}-shapes such that all the \textsc{L}-shapes' anchors lie on the same horizontal line. We show that recognizing grounded \textsc{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 (\textsc{StabGIG}) if there is a grid intersection representation of $G$ in which the same line stabs all its segments. We show that recognizing \textsc{StabGIG} graphs is NP-complete, even when the input graphs are restricted to be bipartite apex graphs of large (but constant) girth. This answers an open question asked by Chaplick \textit{et al.} (\textsc{O}rder, 2018).