**Next:** Problem 71: Stretch-Factor for Points in Convex Position

**Previous:** Problem 69: Isoceles Planar Graph Drawing

- Statement
Is the Yao-Yao Graph a t-spanner for constant t? A geometric graph is a

*t-spanner*(or just a*spanner*) if, for every pair of nodes, the shortest distance between the nodes following the edges of the graph is at most t times the Euclidean distance between them. See below for the definition of the Yao-Yao graph.- Origin
[WL02](?)

- Status/Conjectures
Open.

- Partial and Related Results
The Yao graph Y_k [Yao82] is defined as follows. At each node u, any k equally-separated rays originated at u define k cones. In each cone, choose the shortest edge uv among all edges from u, if there are any, and add a directed edge \overrightarrow{uv} to Y_k. It is known that for the undirected Y_k, k=4, k \ge 6, Y_k a t-spanner (e.g., see [BDD+10]). The Yao-Yao graph YY_k [WL02] starts with the directed Yao graph, and reduces the maximum degree of nodes as follows. At each node u, all

*incoming*edges from each cone are discarded, except for the shortest one \overrightarrow{vu}. And now the result is treated as an undirected graph. Many properties of YY_k have been established, but whether or not YY_k is a t-spanner remains open.- Categories
spanners; geometric graphs

- Entry Revision History
J. O’Rourke, 29 Dec. 2008.

- [BDD+10]
Prosenjit Bose, Mirela Damian, Karim Douieb, Joseph O’Rourke, Ben Seamone, Michiel Smid, and Stefanie Wurher. \pi/2-angle Yao graphs are spanners. arXiv: 1001.2913v1 [cs.CG], January 2010.

- [WL02]
Yu Wang and Xiang-Yang Li. Distributed spanner with bounded degree for wireless ad hoc networks. In

*IPDPS ’02: Proc. of the 16th IEEE Int. Parallel and Distributed Processing Symposium*, pages 194–201, 2002.- [Yao82]
A. C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems.

*SIAM J. Comput.*, 11(4):721–736, 1982.