ICC   25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
artículos
Título:
On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
Autor/es:
L. ALCÓN; M. GUTIERREZ; M. VALENCIA PAVÓN; G. DURÁN; B. RIES; F. BONOMO; M. P. MAZZOLENI; L. ALCÓN; M. GUTIERREZ; M. VALENCIA PAVÓN; G. DURÁN; B. RIES; F. BONOMO; M. P. MAZZOLENI
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2018 vol. 234 p. 12 - 21
ISSN:
0166-218X
Resumen:
Golumbic, Lipshteyn and Stern [12] proved that every graph can be represented as the edgeintersection graph of paths on a grid (EPG graph), i.e., one can associate with each vertexof the graph a nontrivial path on a rectangular grid such that two vertices are adjacent ifand only if the corresponding paths share at least one edge of the grid. For a nonnegativeinteger k, Bk-EPG graphs are defined as EPG graphs admitting a model in which each pathhas 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 B4-EPG graph, by embedding the circleinto a rectangle of the grid. In this paper, we prove that circular-arc graphs are B3-EPG,and that there exist circular-arc graphs which are not B2-EPG. If we restrict ourselves torectangular representations (i.e., the union of the paths used in the model is containedin the boundary of a rectangle of the grid), we obtain EPR (edge intersection of paths ina rectangle) representations. We may define Bk-EPR graphs, k ≥ 0, the same way as BkEPG graphs. Circular-arc graphs are clearly B4-EPR graphs and we will show that thereexist circular-arc graphs that are not B3-EPR graphs. We also show that normal circulararc graphs are B2-EPR graphs and that there exist normal circular-arc graphs that are notB1-EPR graphs. Finally, we characterize B1-EPR graphs by a family of minimal forbiddeninduced subgraphs, and show that they form a subclass of normal Helly circular-arc graphs.© 2016 Elsevier B.V. All rights reserved.