Autor(es)

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

URL Pública

Abstract

Golumbic, Lipshteyn and Stern [12] proved that every graph can be represented as the edge intersection graph of paths on a grid (EPG graph), ie, 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 of a 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 (ie, the union of the paths used in the model is contained in the boundary of a …