INVESTIGADORES
BONOMO Flavia
congresos y reuniones científicas
Título:
Characterising chordal contact B0-VPG graphs
Autor/es:
BONOMO, FLAVIA; MAZZOLENI, MARÍA PIA; REAN, MARIANO; RIES, BERNARD
Lugar:
Marrakesh
Reunión:
Simposio; International Symposium on Combinatorial Optimization (ISCO); 2018
Institución organizadora:
Université Paris Dauphine
Resumen:
A graph G is a B0-VPG graph if it is the vertex intersection graph of horizontal and vertical paths on a grid. A graph G is a contact B0-VPG graph if the vertices can be represented by interiorly disjoint horizontal or vertical paths on a grid and two vertices are adjacent if and only if the corresponding paths touch. In this paper, we present a minimal forbidden induced subgraph characterisation of contact B0-VPG graphs within the class of chordal graphs and provide a polynomial time algorithm for recognising these graphs.