On the Spanning Ratio of Theta 4

Darryl Hill

The Theta 4 graph is a proven spanner, but a tight bound is yet to be achieved. We describe an algorithm that elicits a path in the Theta 4 graph between any two vertices $p$ and $q$, and show that this path is not longer than $11|pq|$. This is an improvement on the current upper bound of approximately $237$. Given that the spanning ratio has a lower bound is $7$, the search for a tight bound is narrowed significantly.