On the Intersection Graphs of Orthogonal Line Segments in the Plane: Characterizations of Some Subclasses of Chordal Graphs
Date
2013Dewey
Principes généraux des mathématiquesSujet
Segment graphs; 2-DIR graphs; Chordal claw-free graphs; Chordal bull-free graphs; Split graphs; Rectangular grid; Vertex intersection graphJournal issue
Graphs and CombinatoricsVolume
29Number
3Publication date
2013Article pages
499-517Publisher
SpringerCollections
Metadata
Show full item recordAuthor
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
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.Related items
Showing items related by title, author, creator and subject.
-
Weighted coloring on planar, bipartite and split graphs: complexity and approximation
Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié -
Isoradial immersions
Boutillier, Cédric; Cimasoni, David; de Tilière, Béatrice (2019) Document de travail / Working paper -
Weighted coloring: further complexity and approximability results
Paschos, Vangelis; Escoffier, Bruno; Monnot, Jérôme (2006) Article accepté pour publication ou publié