Journal article

Characterizations of cographs as intersection graphs of paths on a grid

    2014
Published in:
  • Discrete Applied Mathematics. - 2014, vol. 178, p. 46-57
English A cograph is a graph which does not contain any induced path on four vertices. In this paper, we characterize those cographs that are intersection graphs of paths on a grid in the following two cases: (i) the paths on the grid all have at most one bend and the intersections concern edges (→ B1-EPG); (ii) the paths on the grid are not bended and the intersections concern vertices (→ B0-VPG). In both cases,wegive a characterization by a family of forbidden induced subgraphs.We further present linear- time algorithms to recognize B1-EPG cographs and B0-VPG cographs using their cotree.
Faculty
Faculté des sciences économiques et sociales
Department
Département d'informatique
Language
  • English
Classification
Computer science
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/308613
Statistics

Document views: 7 File downloads:
  • epg.pdf: 4