ICC 25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
congresos y reuniones científicas
Título:
Vertex intersection graphs of paths on a grid: a characterization within block graphs
Autor/es:
BONOMO, FLAVIA; MAZZOLENI, MARÍA PIA; ALCÓN, LILIANA
Lugar:
La Plata
Reunión:
Workshop; VII Latin-American Workshop on Cliques in Graphs; 2016
Institución organizadora:
UNLP
Resumen:
A VPG representation of a graph G is a collection of paths of the twodimensionalgrid where the paths represent the vertices of G in such a waythat two vertices of G are adjacent in G if and only if their correspondingpaths share at least one vertex of the grid. A graph which has a VPGrepresentation is called a VPG graph. In this work, we consider the subclassB0-VPG.A B0-VPG representation of G is a VPG representation in which eachpath in the representation is either a horizontal path or a vertical path onthe grid. A graph is a B0-VPG graph if it has a B0-VPG representation.Recognizing this class is an NP-complete problem, although there existsa polynomial time algorithm for recognizing chordal B0-VPG graphs.In this work, we present a minimal forbidden induced subgraph characterizationof B0-VPG graphs restricted to block graphs. As a byproduct, theproof of the main theorem provides an alternative certifying recognition andrepresentation algorithm for B0-VPG graphs in the class of block graphs.
