Graph spanners: A tutorial review

Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Richard Spence

Research output: Contribution to journalReview articlepeer-review

45 Scopus citations


This survey provides a guiding reference to researchers seeking an overview of the large body of literature about graph spanners. It surveys 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.

Original languageEnglish (US)
Article number100253
JournalComputer Science Review
StatePublished - Aug 2020
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Graph spanners: A tutorial review'. Together they form a unique fingerprint.

Cite this