Gromov hyperbolicity of planar graphs

Alicia Cantón ; Ana Granados ; Domingo Pestana ; José Rodríguez

Open Mathematics, Tome 11 (2013), p. 1817-1830 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2013-01-01

Zbl 1277.05045

EUDML-ID : urn:eudml:doc:269351

Bibliographie

[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 | Zbl 0849.20023

[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] | Zbl 1059.30038

[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] | Zbl 1247.53043

[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] | Zbl 1242.05061

[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 | Zbl 1279.05017

[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] | Zbl 0985.05021

[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 | Zbl 1243.05182

[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 | Zbl 1327.05257

[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 | Zbl 1283.05236

[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] | Zbl 1171.05315

[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 | Zbl 1302.68284

[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] | Zbl 1180.53045

[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 | Zbl 1175.05050

[16] Ghys É., de la Harpe P. (Eds.), Sur les Groupes Hyperboliques d’Après Mikhael Gromov, Progr. Math., 83, Birkhäuser, Boston, 1990 [Crossref] | Zbl 0731.20025

[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] | Zbl 1089.30044

[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] | Zbl 1262.30044

[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] | Zbl 1195.30061

[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] | Zbl 1193.53108

[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] | Zbl 1160.05017

[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] | Zbl 1268.05172

[30] Michel J., Rodríguez J.M., Sigarreta J.M., Villeta M., Hyperbolicity and parameters of graphs, Ars Combin., 2011, 100, 43–63 | Zbl 1265.05200

[31] Ohshika K., Discrete Groups, Transl. Math. Monogr., 207, American Mathematical Society, Providence, 2002 | Zbl 1006.20031

[32] Papasoglu P., Strongly geodesically automatic groups are hyperbolic, Invent. Math., 1995, 121(2), 323–334 http://dx.doi.org/10.1007/BF01884301[Crossref] | Zbl 0834.20040

[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] | Zbl 1239.05141

[34] Portilla A., Rodríguez J.M., Sigarreta J.M., Tourís E., Gromov hyperbolic directed graphs, Acta Math. Appl. Sin. (in press) | Zbl 1339.05324

[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 | Zbl 1339.05324

[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] | Zbl 1047.30028

[37] Portilla A., Rodríguez J.M., Tourís E., Stability of Gromov hyperbolicity, J. Adv. Math. Stud., 2009, 2(2), 77–96 | Zbl 1205.30039

[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] | Zbl 1153.53320

[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] | Zbl 1226.05147

[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] | Zbl 1051.30036

[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] | Zbl 1115.30050

[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] | Zbl 1219.53047

[44] Wu Y., Zhang C., Hyperbolicity and chordality of a graph, Electron. J. Combin., 2011, 18(1), #43 | Zbl 1220.05020