next up previous
Next: Problem 71: Stretch-Factor for Up: The Open Problems Project Previous: Problem 69: Isoceles Planar


Problem 70: Yao-Yao Graph a Spanner?

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 Yk [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 Yk. It is known that for the undirected Yk, k = 4, k≥6, Yk a t-spanner (e.g., see [BDD+10]). The Yao-Yao graph YYk [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 YYk have been established, but whether or not YYk is a t-spanner remains open.
Categories
spanners; geometric graphs
Entry Revision History
J. O'Rourke, 29 Dec. 2008.

Bibliography

BDD+10
Prosenjit Bose, Mirela Damian, Karim Douieb, Joseph O'Rourke, Ben Seamone, Michiel Smid, and Stefanie Wurher.
π/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.


next up previous
Next: Problem 71: Stretch-Factor for Up: The Open Problems Project Previous: Problem 69: Isoceles Planar
The Open Problems Project - December 04, 2015