Autor(es)

Flavia Bonomo-Braberman and María Pía Mazzoleni and Mariano Leonardo Rean and Bernard Ries

URL Pública

Abstract

A graph G is a B 0-VPG graph if one can associate a horizontal or vertical path on a rectangular grid with each vertex such that two vertices are adjacent if and only if the corresponding paths intersect in at least one grid-point. A graph G is a contact B 0-VPG graph if it is a B 0-VPG graph admitting a representation with no one-point paths, no two paths crossing, and no two paths sharing an edge of the grid. In this paper, we present a minimal forbidden induced subgraph characterisation of contact B 0-VPG graphs within four special graph classes: chordal graphs, tree-cographs, P 4-tidy graphs and P 5-free graphs. Moreover, we present a polynomial-time algorithm for recognising chordal contact B 0-VPG graphs.