Diameter Spanners, Eccentricity Spanners, and Approximating Extremal Distances

Understand

The diameter of a graph is one if its most important parameters, being used in many real-word applications.

• In particular, the diameter dictates how fast information can spread throughout data and communication networks.
• Thus, it is a natural question to ask how much can we sparsify a graph and still guarantee that its diameter remains preserved within an approximation $t$.
• This property is captured by the notion of extremal-distance spanners.