Public access from Dec 18, 2019
Université de Fribourg

Characterising Chordal Contact : Bo-VPG Graphs

Bonomo, Flavia ; Mazzoleni, Maria Pia ; Rean, Mariano Leonardo ; Ries, Bernard

In: Lecture Notes in Computer Science, 2018, vol. 10856, p. 89-100

A graph G is a Bo- VPG graph if it is the vertex intersection graph of horizontal and vertical paths on a grid. A graph G is a contact Bo- 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...