Artículo
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. © 2016 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.; Mazzoleni, M.P.; 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é de Fribourg, DIUF, Fribourg, Switzerland Université Paris-13, Sorbonne Paris Cité LIPN, CNRS UMR7030, Villetaneuse, France CONICET, Argentina Délégation at the INRIA Nancy - Grand Est, France |
| Palabras clave: | (normal, Helly) circular-arc graphs; Edge intersection graphs; Forbidden induced subgraphs; Paths on a grid; Powers of cycles; Geometry; Graphic methods; Circular-arc graph; Forbidden induced subgraphs; Intersection graph; Paths on a grid; Powers of cycles; Graph theory |
| Año: | 2018 |
| Volumen: | 234 |
| Página de inicio: | 12 |
| Página de fin: | 21 |
| DOI: | http://dx.doi.org/10.1016/j.dam.2016.08.004 |
| Título revista: | Discrete Applied Mathematics |
| Título revista abreviado: | Discrete Appl Math |
| ISSN: | 0166218X |
| CODEN: | DAMAD |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v234_n_p12_Alcon |
Referencias:
- Alcón, L., Bonomo, F., Durán, G., Gutierrez, M., Mazzoleni, P., Ries, B., Valencia-Pabon, M., On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid (2015) Electron. Notes Discrete Math., 50, pp. 249-254
- 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. Theor. Comput. Sci., 12 (1), pp. 1-12
- Bondy, J.A., Murty, U.S.R., Graph Theory (2007), Springer New York; Cao, Y., Grippo, L.N., Safe, M.D., Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection (2015) Discrete Appl. Math., , http://dx.doi.org/10.1016/j.dam.2015.08.023, in press
- Durán, G., Grippo, L.N., Safe, M.D., 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.C., Morgenststern, G., Approximation algorithms for B1-EPG graphs (2013) Lecture Notes in Comput. Sci., 8037, pp. 328-340
- Francis, M., Hell, P., Stacho, J., Indyk, P., Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm (2015), pp. 1708-1727. , Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA; Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369
- Golumbic, M.C., Hammer, P.L., Stability in circular-arc graphs (1988) J. Algorithms, 9, pp. 314-320
- Golumbic, M.C., Lipshteyn, M., Stern, M., Edge intersection graphs of single bend paths on a grid (2009) Networks, 54, pp. 130-138
- Golumbic, M.C., Lipshteyn, M., Stern, M., Single bend paths on a grid have strong Helly number 4 (2013) Networks, 62, pp. 161-163
- Heldt, D., Knauer, K., Ueckerdt, T., Edge-intersection graphs of grid paths: the bend-number (2014) Discrete Appl. Math., 167, pp. 144-162
- Heldt, D., Knauer, K., Ueckerdt, T., On the bend-number of planar and outerplanar graphs (2014) Discrete Appl. Math., 179, pp. 109-119
- Jamison, B., Olariu, S., A tree representation for P4-sparse graphs (1992) Discrete Appl. Math., 35, pp. 115-129
- Lin, M.C., Soulignac, F.J., Szwracfiter, J.L., Normal Helly circular-arc graphs and its subclasses (2013) Discrete Appl. Math., 161, pp. 1037-1059
- Lin, M.C., Szwarcfiter, J.L., Characterizations and linear time recognition of Helly circular-arc graphs (2006) Lecture Notes in Comput. Sci., 4112, pp. 73-82
- Lin, M.C., Szwarcfiter, J.L., Characterizations and recognition of circular-arc graphs and subclasses: A survey (2009) Discrete Math., 309 (18), 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., Mazzoleni, M.P., Ries, B. & Valencia-Pabon, M. (2018) . On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid. Discrete Applied Mathematics, 234, 12-21.http://dx.doi.org/10.1016/j.dam.2016.08.004
---------- CHICAGO ----------
Alcón, L., Bonomo, F., Durán, G., Gutierrez, M., Mazzoleni, M.P., Ries, B., et al. "On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid" . Discrete Applied Mathematics 234 (2018) : 12-21.http://dx.doi.org/10.1016/j.dam.2016.08.004
---------- MLA ----------
Alcón, L., Bonomo, F., Durán, G., Gutierrez, M., Mazzoleni, M.P., Ries, B., et al. "On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid" . Discrete Applied Mathematics, vol. 234, 2018, pp. 12-21.http://dx.doi.org/10.1016/j.dam.2016.08.004
---------- VANCOUVER ----------
Alcón, L., Bonomo, F., Durán, G., Gutierrez, M., Mazzoleni, M.P., Ries, B., et al. On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid. Discrete Appl Math. 2018;234:12-21.http://dx.doi.org/10.1016/j.dam.2016.08.004
