Thumbnail - Request a copy

Characterizations of cographs as intersection graphs of paths on a grid

Ries, Bernard; Golumbic, Martin Charles; Cohen, Elad (2014), Characterizations of cographs as intersection graphs of paths on a grid, Discrete Applied Mathematics, 178, p. 46-57. 10.1016/j.dam.2014.06.020

Type
Article accepté pour publication ou publié
Date
2014
Journal name
Discrete Applied Mathematics
Volume
178
Publisher
Elsevier
Pages
46-57
Publication identifier
Metadata
Show full item record
Author(s)
Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Golumbic, Martin Charles
Department of Computer Science [Haifa]
Cohen, Elad
Department of Computer Science [Haifa]
Abstract (EN)
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→B1-EPG); (ii) the paths on the grid are not bended and the intersections concern vertices (→B0→B0-VPG). In both cases, we give a characterization by a family of forbidden induced subgraphs. We further present linear-time algorithms to recognize B1B1-EPG cographs and B0B0-VPG cographs using their cotree.
Subjects / Keywords
Induced subgraph; Intersection graph; Grid; Cotree; Cograph