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

Golumbic, Martin Charles; Ries, Bernard

Golumbic, Martin Charles; Ries, Bernard (2013), On the Intersection Graphs of Orthogonal Line Segments in the Plane: Characterizations of Some Subclasses of Chordal Graphs, Graphs and Combinatorics, 29, 3, p. 499-517. 10.1007/s00373-012-1133-7

Type

Article accepté pour publication ou publié

Date

2013

Journal name

Graphs and Combinatorics

Volume

Number

Publisher

Springer

Pages

499-517

Publication identifier

10.1007/s00373-012-1133-7

Metadata

Show full item record

Author(s)

Golumbic, Martin Charles
Department of Computer Science [Haifa]
Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]

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.

Subjects / Keywords

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