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 PIA; RIES, BERNARD; VALENCIA-PABON, MARIO

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2018 vol. 234 p. 12 - 21

0166-218X

Golumbic, Lipshteyn and Stern cite{Golumbic-epg} proved thatevery graph can be represented as the edge intersection graph ofpaths on a grid (EPG graph), i.e., one can associate with eachvertex of the graph a nontrivial path on a rectangular grid suchthat two vertices are adjacent if and only if the correspondingpaths share at least one edge of the grid. For a nonnegativeinteger $k$, $B_k$-EPG graphs are defined as EPG graphs admittinga model in which each path has at most $k$ bends. Circular-arcgraphs are intersection graphs of open arcs of a circle. It iseasy to see that every circular-arc graph is a $B_4$-EPG graph, byembedding the circle into a rectangle of the grid. In this paper,we prove that circular-arc graphs are $B_3$-EPG, and that thereexist circular-arc graphs which are not $B_2$-EPG. If we restrictourselves to rectangular representations (i.e., the union of thepaths used in the model is contained in the boundary of arectangle of the grid), we obtain EPR (edge intersection of pathsin a rectangle) representations. We may define $B_k$-EPR graphs,$kgeq 0$, the same way as $B_k$-EPG graphs. Circular-arc graphsare clearly $B_4$-EPR graphs and we will show that there existcircular-arc graphs that are not $B_3$-EPR graphs. We also showthat normal circular-arc graphs are $B_2$-EPR graphs and thatthere exist normal circular-arc graphs that are not $B_1$-EPRgraphs. Finally, we characterize $B_1$-EPR graphs by a family ofminimal forbidden induced subgraphs, and show that they form asubclass of normal Helly circular-arc graphs.