On the Spanning Ratio of $\Theta_5$

Darryl Hill

Carleton University

The $\Theta_5$-graph is a proven 9.96-spanner. The proof is by induction on the size of the canonical triangle (loosely speaking an isosceles triangle of given angle with two vertices on the boundary). By observing that the closest pair of vertices in the $\Theta_5$-graph has an edge between them, we use induction on the Euclidean distance between two vertices to improve the spanning ratio to 5.70.

We also show that proving the spanning ratio of $\Theta_5$ on a set of points and constraints is much more challenging, and is still technically open. We show some viable, if complex, methods that may or may not bear fruit.