Artículo
On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
Alcón, Liliana Graciela
; Bonomo, Flavia
; Duran, Guillermo Alfredo
; Gutierrez, Marisa
; Mazzoleni, María Pía
; Ries, Bernard; Valencia Pavón, Mario
Fecha de publicación:
01/2018
Editorial:
Elsevier Science
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
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, Bk-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 B4-EPG graph, by embedding the circle into 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 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 Bk-EPR graphs, k≥0, the same way as Bk-EPG graphs. Circular-arc graphs are clearly B4-EPR graphs and we will show that there exist circular-arc graphs that are not B3-EPR graphs. We also show that normal circular-arc graphs are B2-EPR graphs and that there exist normal circular-arc graphs that are not B1-EPR graphs. Finally, we characterize B1-EPR graphs by a family of minimal forbidden induced subgraphs, and show that they form a subclass of normal Helly circular-arc graphs.
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos(ICC)
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Alcón, Liliana Graciela; Bonomo, Flavia; Duran, Guillermo Alfredo; Gutierrez, Marisa; Mazzoleni, María Pía; et al.; On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid; Elsevier Science; Discrete Applied Mathematics; 234; 1-2018; 12-21
Compartir
Altmétricas