Vertex intersection graphs of paths on a grid: characterization within block graphs

ALCÓN, LILIANA; BONOMO, FLAVIA; MAZZOLENI, MARÍA PIA

GRAPHS AND COMBINATORICS

SPRINGER TOKYO

Lugar: Tokyo; Año: 2017 vol. 33 p. 653 - 664

0911-0119

We investigate graphs that can be represented as vertexintersections of horizontal and vertical paths in a grid, the socalled $B_0$-VPG graphs. Recognizing this class is an NP-completeproblem. Although, there exists a polynomial time algorithm forrecognizing chordal $B_0$-VPG graphs. In this paper, we present aminimal forbidden induced subgraph characterization of $B_0$-VPGgraphs restricted to block graphs. As a byproduct, the proof of the maintheorem provides an alternative certifying recognition and representationalgorithm for $B_0$-VPG graphs in the class of block graphs.