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...

Université de Fribourg

On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid

Alcón, Liliana ; Bonomo, Flavia ; Durán, Guillermo ; Gutierrez, Marisa ; Mazzoleni, María Pía ; Ries, Bernard ; Valencia-Pabon, Mario

In: Discrete applied mathematics, 2018, vol. 234, p. 12-21

Golumbic, Lipshteyn and Stern [12] proved that every graph can be represented as the edge intersection graph of paths on a grid (EPG graph), i.e., one can associate with each vertex of the graph a nontrivial path on a rectangular grid such that two vertices are adjacent if and only if the corresponding paths share at least one edge of the grid. For a nonnegative integer k, Bk-EPG graphs are...