On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
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 ed...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , , , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier
2015
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 06487caa a22007217a 4500 | ||
|---|---|---|---|
| 001 | PAPER-13139 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204324.0 | ||
| 008 | 190411s2015 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84953400982 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Alcón, L. | |
| 245 | 1 | 3 | |a On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid |
| 260 | |b Elsevier |c 2015 | ||
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Asinowski, A., Ries, B., Some properties of edge intersection graphs of single-bend paths on a grid (2012) Discrete Math., 312, pp. 427-440 | ||
| 504 | |a 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 | ||
| 504 | |a Biedl, T., Stern, M., On edge intersection graphs of k-bend paths in grids (2010) Discrete Math. Theoret. Comput. Sci., 12, pp. 1-12 | ||
| 504 | |a Bondy, J., Murty, U., (2007) Graph Theory, , Springer, New York | ||
| 504 | |a Cao, Y., Grippo, L., Safe, M., Forbidden induced subgraphs of normal Helly circular-arc graphs: Characterization and detection, , arxiv:1405.0329v1 | ||
| 504 | |a 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 | ||
| 504 | |a Epstein, D., Golumbic, M., Morgenststern, G., Approximation algorithms for B1-EPG graphs (2013) Lect. Notes Comput. Sci., 8037, pp. 328-340 | ||
| 504 | |a Francis, M., Hell, P., Stacho, J., Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm, , arxiv:1408.2639v1 | ||
| 504 | |a Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369 | ||
| 504 | |a Golumbic, M., Lipshteyn, M., Stern, M., Edge intersection graphs of single bend paths on a grid (2009) Networks, 54, pp. 130-138 | ||
| 504 | |a Lin, M., Soulignac, F., Szwracfiter, J., Normal Helly circular-arc graphs and its subclasses (2013) Discrete Appl. Math., 161, pp. 1037-1059 | ||
| 504 | |a Lin, M., Szwarcfiter, J., Characterizations and recognition of circular-arc graphs and subclasses: A survey (2009) Discrete Math., 309, pp. 5618-5635 | ||
| 504 | |a Tucker, A., Characterizing circular-arc graphs (1970) Bull. Amer. Math. Soc., 76, pp. 1257-1260 | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Detalles de la financiación: Fondo Nacional de Desarrollo Científico, Tecnológico y de Innovación Tecnológica, 1140787 | ||
| 536 | |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, 20020130100808BA | ||
| 536 | |a Detalles de la financiación: 13MATH-07 | ||
| 536 | |a Detalles de la financiación: 112-200901-00178, 112-201201-00450CO, PIP 122-01001-00310 | ||
| 536 | |a Detalles de la financiación: Agencia Nacional de Promoción Científica y Tecnológica, 2012-1324, PICT 2010-1970 | ||
| 536 | |a Detalles de la financiación: E-mail addresses: liliana@mate.unlp.edu.ar; fbonomo@dc.uba.ar; gduran@dm.uba.ar; marisa@mate.unlp.edu.ar; pia@mate.unlp.edu.ar; bernard.ries@dauphine.fr; valencia@lipn.univ-paris13.fr. This work was partially supported by MathAmSud Project 13MATH-07 (Argentina–Brazil– Chile–France), UBACyT Grant 20020130100808BA, CONICET PIP 122-01001-00310, 112-200901-00178 and 112-201201-00450CO and ANPCyT PICT 2010-1970 and 2012-1324 (Argentina), FONDECyT Grant 1140787 and Millennium Science Institute “Complex Engineering Systems” (Chile). | ||
| 593 | |a Dto. de Matemática, FCE-UNLP, La Plata, Argentina | ||
| 593 | |a Dto. de Computación, FCEN-UBA, Buenos Aires, Argentina | ||
| 593 | |a Dto. de Matemática e Inst. de Cálculo, FCEN-UBA, Buenos Aires, Argentina | ||
| 593 | |a Dto. de Ingeniería Industrial, FCFM-Univ. de Chile, Santiago, Chile | ||
| 593 | |a Université Paris-Dauphine, LAMSADE, Paris, France | ||
| 593 | |a Université Paris-13, Sorbonne Paris Cité LIPN, CNRS UMR7030, Villetaneuse, France | ||
| 593 | |a Délégation at the INRIA Nancy - Grand Est, France | ||
| 593 | |a CONICET, Argentina | ||
| 690 | 1 | 0 | |a (NORMAL, HELLY) |
| 690 | 1 | 0 | |a CIRCULAR-ARC GRAPHS |
| 690 | 1 | 0 | |a EDGE INTERSECTION GRAPHS |
| 690 | 1 | 0 | |a FORBIDDEN INDUCED SUBGRAPHS |
| 690 | 1 | 0 | |a PATHS ON A GRID |
| 700 | 1 | |a Bonomo, F. | |
| 700 | 1 | |a Durán, G. | |
| 700 | 1 | |a Gutierrez, M. | |
| 700 | 1 | |a Pía Mazzoleni, M. | |
| 700 | 1 | |a Ries, B. | |
| 700 | 1 | |a Valencia-Pabon, M. | |
| 773 | 0 | |d Elsevier, 2015 |g v. 50 |h pp. 249-254 |p Electron. Notes Discrete Math. |x 15710653 |t Electronic Notes in Discrete Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84953400982&doi=10.1016%2fj.endm.2015.07.042&partnerID=40&md5=b1dfb42e95a73625c5d2893527cb8f25 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.endm.2015.07.042 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p249_Alcon |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p249_Alcon |y Registro en la Biblioteca Digital |
| 961 | |a paper_15710653_v50_n_p249_Alcon |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 74092 | ||