Planarity and Hyperbolicity in Graphs Articles uri icon

publication date

  • September 2015

start page

  • 1311

end page

  • 1324

issue

  • 5

volume

  • 31

international standard serial number (ISSN)

  • 0911-0119

electronic international standard serial number (EISSN)

  • 1435-5914

abstract

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

keywords

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