On the Intersection Graphs of Orthogonal Line Segments in the Plane: Characterizations of Some Subclasses of Chordal Graphs

摘要

We investigate here the intersection graphs of horizontal and vertical line segments in the plane, the so called B_0-VP_G graphs. A forbidden induced subgraph characterization of B_0-VP_G split graphs is given, and we present a linear time algorithm to recognize this class. Next, we characterize chordal bull-free B_0-VP_G graphs and chordal claw-free B_0-VP_G graphs.