Planarity and Hyperbolicity in Graphs

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.

Planarity and Hyperbolicity in Graphs Articles