ICC   25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
artículos
Título:
Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs
Autor/es:
MAZZOLENI, MARÍA PÍA; ALCÓN, LILIANA; BONOMO, FLAVIA
Revista:
GRAPHS AND COMBINATORICS
Editorial:
SPRINGER TOKYO
Referencias:
Año: 2017 vol. 33 p. 653 - 664
ISSN:
0911-0119
Resumen:
We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called (Formula presented.)-VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a polynomial time algorithm for recognizing chordal (Formula presented.)-VPG graphs. In this paper, we present a minimal forbidden induced subgraph characterization of (Formula presented.)-VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative certifying recognition and representation algorithm for (Formula presented.)-VPG graphs in the class of block graphs.