Gromov hyperbolicity of planar graphs

• Autorzy: Alicia Cantón , Ana Granados , Domingo Pestana , José Rodríguez
• Języki publikacji: EN

Abstrakty

EN

We prove that under appropriate assumptions adding or removing an infinite amount of edges to a given planar graph preserves its non-hyperbolicity, a result which is shown to be false in general. In particular, we make a conjecture that every tessellation graph of ℝ2 with convex tiles is non-hyperbolic; it is shown that in order to prove this conjecture it suffices to consider tessellation graphs of ℝ2 such that every tile is a triangle and a partial answer to this question is given. A weaker version of this conjecture stating that every tessellation graph of ℝ2 with rectangular tiles is non-hyperbolic is given and partially answered. If this conjecture were true, many tessellation graphs of ℝ2 with tiles which are parallelograms would be non-hyperbolic.

Słowa kluczowe

EN

Planar Graphs; Gromov Hyperbolicity; Infinite Graphs; Geodesics; Tessellation

Kategorie tematyczne

• 05A20: Combinatorial inequalities
• 05C10: Planar graphs; geometric and topological aspects of graph theory
• 05C75: Structural characterization of families of graphs
• 05C63: Infinite graphs

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2013
• Tom: 11
• Numer: 10
• Strony: 1817-1830

Daty

wydano

2013-10-01

online

2013-07-20

Twórcy

autor

Alicia Cantón

• Universidad Politecnica de Madrid, Ciudad Universitaria, Avenida Arco de la Victoria, s/n, 28040, Madrid, Spain

autor

Ana Granados

• Mathematics Department, St. Louis University (Madrid Campus), Avenida del Valle 34, 28003, Madrid, Spain

autor

Domingo Pestana

• Departamento de Matemáticas, Universidad Carlos III de Madrid, Avenida de la Universidad 30, 28911, Leganés, Madrid, Spain

autor

José Rodríguez

• Departamento de Matemáticas, Universidad Carlos III de Madrid, Avenida de la Universidad 30, 28911, Leganés, Madrid, Spain

Bibliografia

• [1] Alonso J., Brady T., Cooper D., Ferlini V., Lustig M., Mihalik M., Shapiro M., Short H., Notes on word hyperbolic groups, In: Group Theory from a Geometrical Viewpoint, Trieste, March 26–April 6, 1990, World Scientific, River Edge, 1991, 3–63
• [2] Balogh Z.M., Buckley S.M., Geometric characterizations of Gromov hyperbolicity, Invent. Math., 2003, 153(2), 261–301 http://dx.doi.org/10.1007/s00222-003-0287-6[Crossref]
• [3] Bermudo S., Rodríguez J.M., Sigarreta J.M., Computing the hyperbolicity constant, Comput. Math. Appl., 2011, 62(12), 4592–4595 http://dx.doi.org/10.1016/j.camwa.2011.10.041[Crossref][WoS]
• [4] Bermudo S., Rodríguez J.M., Sigarreta J.M., Tourís E., Hyperbolicity and complement of graphs, Appl. Math. Letters, 2011, 24(11), 1882–1887 http://dx.doi.org/10.1016/j.aml.2011.05.011[Crossref]
• [5] Bermudo S., Rodríguez J.M., Sigarreta J.M., Vilaire J.-M., Gromov hyperbolic graphs, preprint available at http://gama.uc3m.es/images/gama_papers/jomaro/2010_18_brsv
• [6] Bonk M., Heinonen J., Koskela P., Uniformizing Gromov Hyperbolic Spaces, Astérisque, 270, Paris, 2001
• [7] Brinkmann G., Koolen J.H., Moulton V., On the hyperbolicity of chordal graphs, Ann. Comb., 2001, 5(1), 61–69 http://dx.doi.org/10.1007/s00026-001-8007-7[Crossref]
• [8] Carballosa W., Pestana D., Rodríguez J.M., Sigarreta J.M., Distortion of the hyperbolicity constant of a graph, Electron. J. Combin., 2012, 19(1), #67
• [9] Carballosa W., Portilla A., Rodríguez J.M., Sigarreta J.M., Gromov hyperbolicity of planar graphs and CW complexes, preprint available at http://gama.uc3m.es/images/gama_papers/jomaro/2011_12_cprs_baldosa2.pdf
• [10] Carballosa W., Rodríguez J.M., Sigarreta J.M., Villeta M., On the hyperbolicity constant of line graphs, Electron. J. Combin., 2011, 18(1), #210
• [11] Chavel I., Eigenvalues in Riemannian Geometry, Pure Appl. Math., 115, Academic Press, Orlando, 1984
• [12] Chepoi V., Estellon B., Packing and covering δ-hyperbolic spaces by balls, In: Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Comput. Sci., 4627, Springer, Berlin, 2007, 59–73 http://dx.doi.org/10.1007/978-3-540-74208-1_5[Crossref]
• [13] Eppstein D., Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, June 7–9, 2007, ACM/SIAM, New York/Philadelphia, 29–38
• [14] Frigerio R., Sisto A., Characterizing hyperbolic spaces and real trees, Geom. Dedicata, 2009, 142, 139–149 http://dx.doi.org/10.1007/s10711-009-9363-4[Crossref]
• [15] Gavoille C., Ly O., Distance labeling in hyperbolic graphs, In: Algorithms and Computation, Sanya, December 19–21, 2005, Lecture Notes in Comput. Sci., 3827, Springer, Berlin, 2005, 1071–1079
• [16] Ghys É., de la Harpe P. (Eds.), Sur les Groupes Hyperboliques d’Après Mikhael Gromov, Progr. Math., 83, Birkhäuser, Boston, 1990 [Crossref]
• [17] Gromov M., Hyperbolic groups, In: Essays in Group Theory, Math. Sci. Res. Inst. Publ., 8, Springer, New York, 1987, 75–263 http://dx.doi.org/10.1007/978-1-4613-9586-7_3[Crossref]
• [18] Hästö P.A., Gromov hyperbolicity of the jG and \(\tilde j_G\) metrics, Proc. Amer. Math. Soc., 2006, 134(4), 1137–1142 http://dx.doi.org/10.1090/S0002-9939-05-08053-6[Crossref]
• [19] Hästö P., Lindén H., Portilla A., Rodríguez J.M., Tourís E., Gromov hyperbolicity of Denjoy domains with hyperbolic and quasihyperbolic metrics, J. Math. Soc. Japan, 2012, 64(1), 247–261 http://dx.doi.org/10.2969/jmsj/06410247[WoS][Crossref]
• [20] Hästö P., Portilla A., Rodríguez J.M., Tourís E., Gromov hyperbolic equivalence of the hyperbolic and quasihyperbolic metrics in Denjoy domains, Bull. London Math. Soc., 2010, 42(2), 282–294 http://dx.doi.org/10.1112/blms/bdp125[WoS][Crossref]
• [21] Jonckheere E.A., Contrôle du traffic sur les réseaux à géométrie hyperbolique. Vers une théorie géométrique de la sécurité de l’acheminement de l’information, Journal Européen des Systèmes Automatisés, 2003, 37(2), 145–159 http://dx.doi.org/10.3166/jesa.37.145-159[Crossref]
• [22] Jonckheere E.A., Lohsoonthorn P., A hyperbolic geometry approach to multipath routing, In: 10th Mediterranean Conference on Control and Automation, Lisbon, July 9–12, 2002, available at http://med.ee.nd.edu/MED10/pdf/373.pdf
• [23] Jonckheere E., Lohsoonthorn P., Geometry of network security, In: American Control Conference, 2, Boston, June 30–July 2, 2004, 976–981
• [24] Jonckheere E.A., Lohsoonthorn P., Ariaei F., Upper bound on scaled Gromov-hyperbolic δ, Appl. Math. Comput., 2007, 192(1), 191–204 http://dx.doi.org/10.1016/j.amc.2007.03.001[Crossref][WoS]
• [25] Jonckheere E., Lohsoonthorn P., Bonahon F., Scaled Gromov hyperbolic graphs, J. Graph Theory, 2007, 57(2), 157–180 http://dx.doi.org/10.1002/jgt.20275[Crossref]
• [26] Kanai M., Rough isometries, and combinatorial approximations of geometries of noncompact Riemannian manifolds, J. Math. Soc. Japan, 1985, 37(3), 391–413 http://dx.doi.org/10.2969/jmsj/03730391[Crossref]
• [27] Koolen J.H., Moulton V., Hyperbolic bridged graphs, European J. Combin., 2002, 23(6), 683–699 http://dx.doi.org/10.1006/eujc.2002.0591[Crossref]
• [28] Krauthgamer R., Lee J.R., Algorithms on negatively curved spaces, preprint available at http://homes.cs.washington.edu/~jrl/papers/kl06-neg.pdf
• [29] Michel J., Rodríguez J.M., Sigarreta J.M., Villeta M., Gromov hyperbolicity in Cartesian product graphs, Proc. Indian Acad. Sci. Math. Sci., 2010, 120(5), 593–609 http://dx.doi.org/10.1007/s12044-010-0048-6[Crossref]
• [30] Michel J., Rodríguez J.M., Sigarreta J.M., Villeta M., Hyperbolicity and parameters of graphs, Ars Combin., 2011, 100, 43–63
• [31] Ohshika K., Discrete Groups, Transl. Math. Monogr., 207, American Mathematical Society, Providence, 2002
• [32] Papasoglu P., Strongly geodesically automatic groups are hyperbolic, Invent. Math., 1995, 121(2), 323–334 http://dx.doi.org/10.1007/BF01884301[Crossref]
• [33] Pestana D., Rodríguez J.M., Sigarreta J.M., Villeta M., Gromov hyperbolic cubic graphs, Cent. Eur. J. Math., 2012, 10(3), 1141–1151 http://dx.doi.org/10.2478/s11533-012-0036-4[Crossref][WoS]
• [34] Portilla A., Rodríguez J.M., Sigarreta J.M., Tourís E., Gromov hyperbolic directed graphs, Acta Math. Appl. Sin. (in press)
• [35] Portilla A., Rodríguez J.M., Sigarreta J.M., Vilaire J.-M., Gromov hyperbolic tessellation graphs, Util. Math. (in press), preprint available at http://gama.uc3m.es/images/gama_papers/jomaro/2011_2_prsv_baldosa.pdf
• [36] Portilla A., Rodríguez J.M., Tourís E., Gromov hyperbolicity through decomposition of metric spaces. II, J. Geom. Anal., 2004, 14(1), 123–149 http://dx.doi.org/10.1007/BF02921869[Crossref]
• [37] Portilla A., Rodríguez J.M., Tourís E., Stability of Gromov hyperbolicity, J. Adv. Math. Stud., 2009, 2(2), 77–96
• [38] Portilla A., Tourís E., A characterization of Gromov hyperbolicity of surfaces with variable negative curvature, Publ. Mat., 2009, 53(1), 83–110 [Crossref]
• [39] Rodríguez J.M., Sigarreta J.M., Vilaire J.-M., Villeta M., On the hyperbolicity constant in graphs, Discrete Math., 2011, 311(4), 211–219 http://dx.doi.org/10.1016/j.disc.2010.11.005[WoS][Crossref]
• [40] Rodríguez J.M., Tourís E., Gromov hyperbolicity through decomposition of metric spaces, Acta Math. Hungar., 2004, 103(1–2), 107–138 http://dx.doi.org/10.1023/B:AMHU.0000028240.16521.9d[Crossref]
• [41] Rodríguez J.M., Tourís E., Gromov hyperbolicity of Riemann surfaces, Acta Math. Sin. (Engl. Ser.), 2007, 23(2), 209–228 http://dx.doi.org/10.1007/s10114-005-0547-z[Crossref]
• [42] Shavitt Y., Tankel T., Hyperbolic embedding of internet graph for distance estimation and overlay construction, IEEE/ACM Transactions on Networking, 2008, 16(1), 25–36 http://dx.doi.org/10.1109/TNET.2007.899021[Crossref][WoS]
• [43] Tourís E., Graphs and Gromov hyperbolicity of non-constant negatively curved surfaces, J. Math. Anal. Appl., 2011, 380(2), 865–881 http://dx.doi.org/10.1016/j.jmaa.2011.02.067[Crossref]
• [44] Wu Y., Zhang C., Hyperbolicity and chordality of a graph, Electron. J. Combin., 2011, 18(1), #43

Identyfikatory

DOI

10.2478/s11533-013-0286-9