Recognizing Geometric Intersection Graphs Stabbed by a Line

Dibyayan Chakraborty, Kshitij Gajjar, Irena Rusu

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 mad…