# Graph Spanners: A Tutorial Review

arXiv: https://arxiv.org/abs/1909.03152 · HTML: https://mlsanity.com/paper/1909.03152/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2019.

## Built on by (most cited first, 4 of 4)

- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [Graph Distillation with Eigenbasis Matching](https://mlsanity.com/paper/2310.09202/) (2023)
- [Stars: Tera-Scale Graph Building for Clustering and Graph Learning](https://mlsanity.com/paper/2212.02635/) (2022)
- [Temporal Network Creation Games](https://mlsanity.com/paper/2305.07494/) (2023)

## Abstract (arXiv)

This tutorial review provides a guiding reference to researchers who want to have an overview of the large body of literature about graph spanners. It reviews the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.