Abstract
Using the characteristic property of chordal graphs that they are the intersection graphs of subtrees of a tree, Erich Prisner showed that every chordal graph admits an eccentricity 2-approximating spanning tree. That is, every chordal graph G has a spanning tree T such that ecc(T) (v) - ecc(G)(v) <= 2 for every vertex v, where ecc(G)(v) (ecc(T) (v)) is the eccentricity of a vertex v in G (in T, respectively). Using only metric properties of graphs, we extend that result to a much larger family of graphs containing among others chordal graphs and the underlying graphs of 7-systolic complexes. Furthermore, based on our approach, we propose two heuristics for constructing eccentricity k-approximating trees with small values of k for general unweighted graphs. We validate those heuristics on a set of real-world networks and demonstrate that all those networks have very good eccentricity approximating trees.