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