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

LILIANA ALCÓN; FLAVIA BONOMO; GUILLERMO DURÁN; MARISA GUTIERREZ; MARÍA PÍA MAZZOLENI; BERNARD RIES; MARIO VALENCIA-PABON

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

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

0166-218X

Golumbic, Lipshteyn and Stern 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, B_{k}-EPG graphs are defined as EPG graphs admitting a model in which each path has at most k bends. Circular-arc graphs are intersection graphs of open arcs ofa circle. It is easy to see that every circular-arc graph is a B_{4}-EPG graph, by embedding the circle into a rectangle of the grid. In this paper, we prove that circular-arc graphs are B_{3}-EPG, and that there exist circular-arc graphs which are not B_{2}-EPG. If we restrict ourselves to rectangular representations (i.e., the union of the paths used in the model is contained in the boundary of a rectangle of the grid), we obtain EPR (edge intersection of paths in a rectangle) representations. We may define B_{k}-EPR graphs, k>=0, the same way as B_{k}-EPG graphs. Circular-arc graphs are clearly B_{4}-EPR graphs and we will show that there exist circular-arc graphs that are not B_{3}-EPR graphs. We also show that normal circular-arc graphs are B_{2}-EPR graphs and that there exist normal circular-arc graphs that are not B_{1}-EPR graphs. Finally, we characterize B_{1}-EPR graphs by a family of minimal forbidden induced subgraphs, and show that they form a subclass of normal Helly circular-arcgraphs.