Characterizations of cographs as intersection graphs of paths on a grid
- Cohen, Elad University of Haifa, Israel
- Golumbic, Martin Charles University of Haifa, Israel
- Ries, Bernard Université Paris-Dauphine, France
-
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 et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 328825
- DOI 10.1016/j.dam.2014.06.020
- Persistent URL
- https://folia.unifr.ch/unifr/documents/308613
Statistics
Document views: 63
File downloads:
- epg.pdf: 174