Low Distortion Spanners

A

spanner

of an undirected unweighted graph is a subgraph that approximates the distance metric of the original graph with some specified accuracy. Specifically, we say

H

 ⊆ 

G

is an

f

-spanner of

G

if any two vertices

u

,

v

at distance

d

in

G

are at distance at most

f

(

d

) in

H

. There is clearly some tradeoff between the sparsity of

H

and the distortion function

f

, though the nature of this tradeoff is still poorly understood.

In this paper we present a simple, modular framework for constructing sparse spanners that is based on interchangable components called

connection schemes

. By assembling connection schemes in different ways we can recreate the additive 2- and 6-spanners of Aingworth et al. and Baswana et al. and improve on the (1 + 

ε

,

β

)-spanners of Elkin and Peleg, the sublinear additive spanners of Thorup and Zwick, and the (non constant) additive spanners of Baswana et al. Our constructions rival the simplicity of all comparable algorithms and provide substantially better spanners, in some cases reducing the density

doubly

exponentially.