  In this paper, we study Gromov hyperbolicity and related parameters, that
represent how close (locally) a metric space is to a tree from a metric point
of view. The study of Gromov hyperbolicity for geodesic metric spaces can be
reduced to the study of graph hyperbolicity. The main contribution of this
paper is a new characterization of the hyperbolicity of graphs. This
characterization has algorithmic implications in the field of large-scale
network analysis. A sharp estimate of graph hyperbolicity is useful, e.g., in
embedding an undirected graph into hyperbolic space with minimum distortion
[Verbeek and Suri, SoCG'14]. The hyperbolicity of a graph can be computed in
polynomial-time, however it is unlikely that it can be done in subcubic time.
This makes this parameter difficult to compute or to approximate on large
graphs. Using our new characterization of graph hyperbolicity, we provide a
simple factor 8 approximation algorithm for computing the hyperbolicity of an
$n$-vertex graph $G=(V,E)$ in optimal time $O(n^2)$ (assuming that the input is
the distance matrix of the graph). This algorithm leads to constant factor
approximations of other graph-parameters related to hyperbolicity (thinness,
slimness, and insize). We also present the first efficient algorithms for exact
computation of these parameters. All of our algorithms can be used to
approximate the hyperbolicity of a geodesic metric space.
  We also show that a similar characterization of hyperbolicity holds for all
geodesic metric spaces endowed with a geodesic spanning tree. Along the way, we
prove that any complete geodesic metric space $(X,d)$ has such a geodesic
spanning tree. We hope that this fundamental result can be useful in other
contexts.
