On the bend number of circulararc graphs as edge intersection graphs of paths on a grid

Alcón, Liliana
National University of La Plata

Bonomo, Flavia
University of Buenos Aires, CONICET

Durán, Guillermo
University of Buenos Aires, University of Chile, CONICET

Gutierrez, Marisa
National University of La Plata, CONICET

Mazzoleni, María Pía
National University of La Plata, CONICET

Ries, Bernard
University of Fribourg

ValenciaPabon, Mario
Université Paris13
Show more…
Published in:
 Discrete applied mathematics.  2018, vol. 234, p. 1221
English
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, BkEPG graphs are defined as EPG graphs admitting a model in which each path has at most k bends. Circulararc graphs are intersection graphs of open arcs of a circle. It is easy to see that every circulararc graph is a B4EPG graph, by embedding the circle into a rectangle of the grid. In this paper, we prove that circulararc graphs are B3EPG, and that there exist circulararc graphs which are not B2EPG. 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 BkEPR graphs, k ≥ 0, the same way as Bk EPG graphs. Circulararc graphs are clearly B4EPR graphs and we will show that there exist circulararc graphs that are not B3EPR graphs. We also show that normal circulararc graphs are B2EPR graphs and that there exist normal circulararc graphs that are not B1EPR graphs. Finally, we characterize B1EPR graphs by a family of minimal forbidden induced subgraphs, and show that they form a subclass of normal Helly circulararc graphs.

Faculty
 Faculté des sciences économiques et sociales

Department
 Département d'informatique

Language


Classification

Economics

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/307803
Statistics
Document views: 8
File downloads: