The Kirkpatrick graph: a new type of spanner with small diameter
Chris Hoedemakers
Eindhoven University of Technology

Geometric $t$-spanners are graphs for which it holds that between any two vertices $u$ and $w$ in the graph, there exists a path of length $≤ t \cdot |uw|$, where $|uw|$ is the Euclidean distance between $u$ and $w$. We define $t$ to be the spanning ratio of the spanner. An additional characteristic that may be taken into account when studying spanners is the diameter of the spanner. For a $t$-spanner with diameter $d$ it holds that between any two vertices $u$ and $w$ in the graph, there exists a path of length $≤ t \cdot |uw|$, consisting of $≤ d$ edges.

The spanner introduced here is based on the Kirkpatrick point location hierarchy. We show that it has spanning ratio 2 and diameter $O(\log n)$, where $n$ is the number of vertices in the graph. The Kirkpatrick graph moreover has the favorable property that it contains $O(n)$ edges in total.