---
tag: V4F9Q4JCA6
kind: concept
name: Spanner
aliases: [graph-spanner, spanner-graph-theory]
sources:
  - wikipedia: en:325802@r1373839425
    locator: Glossary of graph theory, section S
    note: adopted
    mention: wikipedia://en/325802#HU7W
    sections: [Summary]
inventory: [R48YT9RKT6]
---

## Summary

A spanner is a (usually sparse) graph whose shortest path distances approximate those in a dense graph or other metric space. Variations include geometric spanners, graphs whose vertices are points in a geometric space; tree spanners, spanning trees of a graph whose distances approximate the graph distances, and graph spanners, sparse subgraphs of a dense graph whose distances approximate the original graph's distances. A greedy spanner is a graph spanner constructed by a greedy algorithm, generally one that considers all edges from shortest to longest and keeps the ones that are needed to preserve the distance approximation.