Mostrar el registro sencillo del ítem
dc.contributor.author
Alcón, Liliana Graciela
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Bonomo, Flavia
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Duran, Guillermo Alfredo
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Gutierrez, Marisa
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Mazzoleni, María Pía
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Ries, Bernard
dc.contributor.author
Valencia Pavón, Mario
dc.date.available
2019-09-09T17:30:39Z
dc.date.issued
2018-01
dc.identifier.citation
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
dc.identifier.issn
0166-218X
dc.identifier.uri
http://hdl.handle.net/11336/83118
dc.description.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), 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.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.subject
(Normal, Helly) Circular-Arc Graphs
dc.subject
Edge Intersection Graphs
dc.subject
Forbidden Induced Subgraphs
dc.subject
Paths on A Grid
dc.subject
Powers of Cycles
dc.subject.classification
Otras Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2019-08-08T19:11:34Z
dc.journal.volume
234
dc.journal.pagination
12-21
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Alcón, Liliana Graciela. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - La Plata; Argentina. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina
dc.description.fil
Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Buenos Aires. Facultad de Cs.exactas y Naturales. Departamento de Computación. Algoritmos, Complejidad y Aplicaciones; Argentina
dc.description.fil
Fil: Duran, Guillermo Alfredo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Universidad de Chile; Chile
dc.description.fil
Fil: Gutierrez, Marisa. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - La Plata; Argentina. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina
dc.description.fil
Fil: Mazzoleni, María Pía. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - La Plata; Argentina. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina
dc.description.fil
Fil: Ries, Bernard. Université de Fribourg; Suiza
dc.description.fil
Fil: Valencia Pavón, Mario. Universite de Paris 13-Nord. Laboratoire d'informatique de L'Université Paris-Nord; Francia
dc.journal.title
Discrete Applied Mathematics
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X16303687
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2016.08.004
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1506.08750
Archivos asociados