Artículo
Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs
Fecha de publicación:
07/2017
Editorial:
Springer Tokyo
Revista:
Graphs And Combinatorics
ISSN:
0911-0119
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called B0-VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a polynomial time algorithm for recognizing chordal B0-VPG graphs. In this paper, we present a minimal forbidden induced subgraph characterization of B0-VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative certifying recognition and representation algorithm for B0-VPG graphs in the class of block graphs.
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos(ICC)
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Alcón, Liliana Graciela; Bonomo, Flavia; Mazzoleni, María Pía; Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs; Springer Tokyo; Graphs And Combinatorics; 33; 4; 7-2017; 653-664
Compartir
Altmétricas