• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
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
29
Number
3
Publication date
2013
Article pages
499-517
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s00373-012-1133-7
URI
https://basepub.dauphine.fr/handle/123456789/8139
Collections
  • LAMSADE : Publications
Metadata
Show full item record
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.

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é

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.