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

摘要

AbstractGolumbic, 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 integerk,Bk-EPG graphs are defined as EPG graphs admitting a model in which each path has at mostkbends. Circular-arc graphs are intersection graphs of open arcs of a circle. It is easy to see that every circular-arc graph is aB4-EPG graph, by embedding the circle into a rectangle of the grid. In this paper, we prove that circular-arc graphs areB3-EPG, and that there exist circular-arc graphs