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

Date

2013

Dewey

Principes généraux des mathématiques

Sujet

Segment graphs; 2-DIR graphs; Chordal claw-free graphs; Chordal bull-free graphs; Split graphs; Rectangular grid; Vertex intersection graph

Journal issue

Graphs and Combinatorics

Volume

Number

Publication date

2013

Article pages

499-517

Publisher

Springer

Author

Golumbic, Martin Charles

87696 Department of Computer Science [Haifa]

Ries, Bernard

989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]

Type

Article accepté pour publication ou publié

Abstract (EN)

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