Artículo
Abstract:
Golumbic, Lipshteyn and Stern proved that every graph can be represented as the edge intersection graph of paths on a grid, i.e., one can associate to each vertex of the graph a nontrivial path on a 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 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 B4-EPG, by embedding the circle into a rectangle of the grid. In this paper we prove that every circular-arc graph is B3-EPG, but if we restrict ourselves to rectangular representations there exist some graphs that require paths with four bends. We also show that normal circular-arc graphs admit rectangular representations with at most two bends per path. Moreover, we characterize graphs admitting a rectangular representation with at most one bend per path by forbidden induced subgraphs, and we show that they are a subclass of normal Helly circular-arc graphs. © 2015 Elsevier B.V.
Registro:
| Documento: | Artículo |
| Título: | On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid |
| Autor: | Alcón, L.; Bonomo, F.; Durán, G.; Gutierrez, M.; Pía Mazzoleni, M.; Ries, B.; Valencia-Pabon, M. |
| Filiación: | Dto. de Matemática, FCE-UNLP, La Plata, Argentina Dto. de Computación, FCEN-UBA, Buenos Aires, Argentina Dto. de Matemática e Inst. de Cálculo, FCEN-UBA, Buenos Aires, Argentina Dto. de Ingeniería Industrial, FCFM-Univ. de Chile, Santiago, Chile Université Paris-Dauphine, LAMSADE, Paris, France Université Paris-13, Sorbonne Paris Cité LIPN, CNRS UMR7030, Villetaneuse, France Délégation at the INRIA Nancy - Grand Est, France CONICET, Argentina |
| Palabras clave: | (normal, Helly); Circular-arc graphs; Edge intersection graphs; Forbidden induced subgraphs; Paths on a grid |
| Año: | 2015 |
| Volumen: | 50 |
| Página de inicio: | 249 |
| Página de fin: | 254 |
| DOI: | http://dx.doi.org/10.1016/j.endm.2015.07.042 |
| Título revista: | Electronic Notes in Discrete Mathematics |
| Título revista abreviado: | Electron. Notes Discrete Math. |
| ISSN: | 15710653 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p249_Alcon |
Referencias:
- Asinowski, A., Ries, B., Some properties of edge intersection graphs of single-bend paths on a grid (2012) Discrete Math., 312, pp. 427-440
- Asinowski, A., Suk, A., Edge intersection graphs of systems of paths on a grid with a bounded number of bends (2009) Discrete Appl. Math., 157, pp. 3174-3180
- Biedl, T., Stern, M., On edge intersection graphs of k-bend paths in grids (2010) Discrete Math. Theoret. Comput. Sci., 12, pp. 1-12
- Bondy, J., Murty, U., (2007) Graph Theory, , Springer, New York
- Cao, Y., Grippo, L., Safe, M., Forbidden induced subgraphs of normal Helly circular-arc graphs: Characterization and detection, , arxiv:1405.0329v1
- Durán, G., Grippo, L., Safe, M., Structural results on circular-arc graphs and circle graphs: a survey and the main open problems (2014) Discrete Appl. Math., 164, pp. 427-443
- Epstein, D., Golumbic, M., Morgenststern, G., Approximation algorithms for B1-EPG graphs (2013) Lect. Notes Comput. Sci., 8037, pp. 328-340
- Francis, M., Hell, P., Stacho, J., Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm, , arxiv:1408.2639v1
- Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369
- Golumbic, M., Lipshteyn, M., Stern, M., Edge intersection graphs of single bend paths on a grid (2009) Networks, 54, pp. 130-138
- Lin, M., Soulignac, F., Szwracfiter, J., Normal Helly circular-arc graphs and its subclasses (2013) Discrete Appl. Math., 161, pp. 1037-1059
- Lin, M., Szwarcfiter, J., Characterizations and recognition of circular-arc graphs and subclasses: A survey (2009) Discrete Math., 309, pp. 5618-5635
- Tucker, A., Characterizing circular-arc graphs (1970) Bull. Amer. Math. Soc., 76, pp. 1257-1260
Citas:
---------- APA ----------
Alcón, L., Bonomo, F., Durán, G., Gutierrez, M., Pía Mazzoleni, M., Ries, B. & Valencia-Pabon, M. (2015) . On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid. Electronic Notes in Discrete Mathematics, 50, 249-254.http://dx.doi.org/10.1016/j.endm.2015.07.042
---------- CHICAGO ----------
Alcón, L., Bonomo, F., Durán, G., Gutierrez, M., Pía Mazzoleni, M., Ries, B., et al. "On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid" . Electronic Notes in Discrete Mathematics 50 (2015) : 249-254.http://dx.doi.org/10.1016/j.endm.2015.07.042
---------- MLA ----------
Alcón, L., Bonomo, F., Durán, G., Gutierrez, M., Pía Mazzoleni, M., Ries, B., et al. "On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid" . Electronic Notes in Discrete Mathematics, vol. 50, 2015, pp. 249-254.http://dx.doi.org/10.1016/j.endm.2015.07.042
---------- VANCOUVER ----------
Alcón, L., Bonomo, F., Durán, G., Gutierrez, M., Pía Mazzoleni, M., Ries, B., et al. On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid. Electron. Notes Discrete Math. 2015;50:249-254.http://dx.doi.org/10.1016/j.endm.2015.07.042
