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 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.

Bibliography

[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.