On the Spanning Ratio of Yao 4
Darryl Hill
Carleton University

Yao graphs are a family of geometric graphs with a simple construction and linear number of edges. Yao 2 and Yao 3 are known to not be spanners; Yao 4 is thus the Yao graph with the least number of edges that is still a spanner. The known upper bound on the spanning ratio of Yao 4 has recently been improved from around 492.22 to around 54.62. I will briefly talk of how these bounds are obtained, and then give ways that these techniques can be improved. I'll give a construction for a possible improvement of the spanning ratio of Yao 4 to $5+\sqrt{2}$, or around 6.41. This is significant not only because it would represent an improvement, but also because the sister graph of the Yao 4 graph, the Theta 4 graph, has a lower bound on its spanning ratio of 7.