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

Thumbnail
Date
2013
Indexation documentaire
Principes généraux des mathématiques
Subject
Segment graphs; 2-DIR graphs; Chordal claw-free graphs; Chordal bull-free graphs; Split graphs; Rectangular grid; Vertex intersection graph
Nom de la revue
Graphs and Combinatorics
Volume
29
Numéro
3
Date de publication
2013
Pages article
499-517
Nom de l'éditeur
Springer
DOI
http://dx.doi.org/10.1007/s00373-012-1133-7
URI
https://basepub.dauphine.fr/handle/123456789/8139
Collections
Métadonnées
Afficher la notice complète
Auteur
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é
Résumé en anglais
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.