Planarity and Hyperbolicity in Graphs Articles uri icon

publication date

  • September 2015

start page

  • 1311

end page

  • 1324


  • 5


  • 31

International Standard Serial Number (ISSN)

  • 0911-0119

Electronic International Standard Serial Number (EISSN)

  • 1435-5914


  • If X is a geodesic metric space and x1,x2,x3 are three points in X , a geodesic triangle T={x1,x2,x3} is the union of three geodesics [x1x2] , [x2x3] and [x3x1] in X . The space X is delta -hyperbolic ( in the Gromov sense ) if any side of T is contained in a delta -neighborhood of the union of the two other sides, for every geodesic triangle T in X . The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. In this paper we obtain criteria which allow us to decide, for a large class of graphs, whether they are hyperbolic or not. We are especially interested in the planar graphs which are the "boundary" (the 1 -skeleton) of a tessellation of the Euclidean plane. Furthermore, we prove that a graph obtained as the 1 -skeleton of a general CW 2 -complex is hyperbolic if and only if its dual graph is hyperbolic.


  • tessellation; planar graph; gromov hyperbolicity; cw complex; dual graph