Gromov hyperbolicity of planar graphs

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

Open Mathematics (2013)

  • Volume: 11, Issue: 10, page 1817-1830
  • ISSN: 2391-5455

Abstract

top
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.

How to cite

top

Alicia Cantón, et al. "Gromov hyperbolicity of planar graphs." Open Mathematics 11.10 (2013): 1817-1830. <http://eudml.org/doc/269351>.

@article{AliciaCantón2013,
abstract = {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.},
author = {Alicia Cantón, Ana Granados, Domingo Pestana, José Rodríguez},
journal = {Open Mathematics},
keywords = {Planar Graphs; Gromov Hyperbolicity; Infinite Graphs; Geodesics; Tessellation; planar graphs; Gromov hyperbolicity; infinite graphs; geodesics; tessellation},
language = {eng},
number = {10},
pages = {1817-1830},
title = {Gromov hyperbolicity of planar graphs},
url = {http://eudml.org/doc/269351},
volume = {11},
year = {2013},
}

TY - JOUR
AU - Alicia Cantón
AU - Ana Granados
AU - Domingo Pestana
AU - José Rodríguez
TI - Gromov hyperbolicity of planar graphs
JO - Open Mathematics
PY - 2013
VL - 11
IS - 10
SP - 1817
EP - 1830
AB - 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.
LA - eng
KW - Planar Graphs; Gromov Hyperbolicity; Infinite Graphs; Geodesics; Tessellation; planar graphs; Gromov hyperbolicity; infinite graphs; geodesics; tessellation
UR - http://eudml.org/doc/269351
ER -

References

top
  1. [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 Zbl0849.20023
  2. [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] Zbl1059.30038
  3. [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] Zbl1247.53043
  4. [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] Zbl1242.05061
  5. [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 Zbl1279.05017
  6. [6] Bonk M., Heinonen J., Koskela P., Uniformizing Gromov Hyperbolic Spaces, Astérisque, 270, Paris, 2001 
  7. [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] Zbl0985.05021
  8. [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 Zbl1243.05182
  9. [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 Zbl1327.05257
  10. [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 Zbl1283.05236
  11. [11] Chavel I., Eigenvalues in Riemannian Geometry, Pure Appl. Math., 115, Academic Press, Orlando, 1984 
  12. [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] Zbl1171.05315
  13. [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 Zbl1302.68284
  14. [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] Zbl1180.53045
  15. [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 Zbl1175.05050
  16. [16] Ghys É., de la Harpe P. (Eds.), Sur les Groupes Hyperboliques d’Après Mikhael Gromov, Progr. Math., 83, Birkhäuser, Boston, 1990 [Crossref] Zbl0731.20025
  17. [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. [18] Hästö P.A., Gromov hyperbolicity of the jG and j ˜ G metrics, Proc. Amer. Math. Soc., 2006, 134(4), 1137–1142 http://dx.doi.org/10.1090/S0002-9939-05-08053-6[Crossref] Zbl1089.30044
  19. [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] Zbl1262.30044
  20. [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] Zbl1195.30061
  21. [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. [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. [23] Jonckheere E., Lohsoonthorn P., Geometry of network security, In: American Control Conference, 2, Boston, June 30–July 2, 2004, 976–981 
  24. [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] Zbl1193.53108
  25. [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] Zbl1160.05017
  26. [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. [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. [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. [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] Zbl1268.05172
  30. [30] Michel J., Rodríguez J.M., Sigarreta J.M., Villeta M., Hyperbolicity and parameters of graphs, Ars Combin., 2011, 100, 43–63 Zbl1265.05200
  31. [31] Ohshika K., Discrete Groups, Transl. Math. Monogr., 207, American Mathematical Society, Providence, 2002 Zbl1006.20031
  32. [32] Papasoglu P., Strongly geodesically automatic groups are hyperbolic, Invent. Math., 1995, 121(2), 323–334 http://dx.doi.org/10.1007/BF01884301[Crossref] Zbl0834.20040
  33. [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] Zbl1239.05141
  34. [34] Portilla A., Rodríguez J.M., Sigarreta J.M., Tourís E., Gromov hyperbolic directed graphs, Acta Math. Appl. Sin. (in press) Zbl1339.05324
  35. [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 Zbl1339.05324
  36. [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] Zbl1047.30028
  37. [37] Portilla A., Rodríguez J.M., Tourís E., Stability of Gromov hyperbolicity, J. Adv. Math. Stud., 2009, 2(2), 77–96 Zbl1205.30039
  38. [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] Zbl1153.53320
  39. [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] Zbl1226.05147
  40. [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] Zbl1051.30036
  41. [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] Zbl1115.30050
  42. [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. [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] Zbl1219.53047
  44. [44] Wu Y., Zhang C., Hyperbolicity and chordality of a graph, Electron. J. Combin., 2011, 18(1), #43 Zbl1220.05020

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.