Characterizations of cographs as intersection graphs of paths on a grid
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 ? B 1 -EPG); (ii) the paths on the grid are not bended and the intersections concern vertices (?B0 ? B 0 -VPG). In both cases, we give a characterization by a family of forbidden induced subgraphs. We further present linear-time algorithms to recognize B1 B 1 -EPG cographs and B0 B 0 -VPG cographs using their cotree.
cograph intersection graph grid induced subgraph cotree