  We introduce notions of certificates allowing to bound eccentricities in a
graph. In particular , we revisit radius (minimum eccentricity) and diameter
(maximum eccentricity) computation and explain the efficiency of practical
radius and diameter algorithms by the existence of small certificates for
radius and diameter plus few additional properties. We show how such
computation is related to covering a graph with certain balls or complementary
of balls. We introduce several new algorithmic techniques related to
eccentricity computation and propose algorithms for radius, diameter and all
eccentricities with theoretical guarantees with respect to certain graph
parameters. This is complemented by experimental results on various real-world
graphs showing that these parameters appear to be low in practice. We also
obtain refined results in the case where the input graph has low doubling
dimension, has low hyperbolicity, or is chordal.
