On the Intersection Graphs of Orthogonal Line Segments in the Plane: Characterizations of Some Subclasses of Chordal Graphs
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
2013Journal name
Graphs and CombinatoricsVolume
29Number
3Publisher
Springer
Pages
499-517
Publication identifier
Metadata
Show full item recordAuthor(s)
Golumbic, Martin CharlesDepartment 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 graphRelated items
Showing items related by title and author.
-
Ries, Bernard; Golumbic, Martin Charles; Cohen, Elad (2014) Article accepté pour publication ou publié
-
Ries, Bernard; Monnot, Jérôme; Lozin, Vadim (2015) Article accepté pour publication ou publié
-
Lozin, Vadim; Monnot, Jérôme; Ries, Bernard (2013) Communication / Conférence
-
Ries, Bernard; Asinowski, Andrei (2012) Article accepté pour publication ou publié
-
Ries, Bernard; Pop, Petrica; Monnot, Jérôme; Demange, Marc (2014) Article accepté pour publication ou publié