Pi/2-Angle Yao Graphs are Spanners

Abstract

We show that the Yao graph Y4 in the L2 metric is a spanner with stretch factor 8(29+23sqrt(2)). Enroute to this, we also show that the Yao graph Y4 in the Linf metric is a planar spanner with stretch factor 8.

20 pages, 9 figures

Cited by in corpus (3)

• The ${\theta }_5$-graph is a spanner
• Routing in Polygonal Domains
• Spanners for Directed Transmission Graphs