Characterising chordal contact B0-VPG graphs

FLAVIA BONOMO; MARÍA PÍA MAZZOLENI; MARIANO LEONARDO REAN; BERNARD RIES

Marrakesh

Simposio; International Symposium on Combinatorial Optimization; 2018

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.