Next: Problem 71: StretchFactor for
Up: The Open Problems Project
Previous: Problem 69: Isoceles Planar
Problem 70: YaoYao Graph a Spanner?
 Statement
 Is the YaoYao Graph
a tspanner for constant t?
A geometric graph is a tspanner
(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 YaoYao 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 equallyseparated 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
to Y_{k}.
It is known that for the undirected Y_{k},
k = 4, k≥6, Y_{k} a tspanner
(e.g., see [BDD+10]).
The YaoYao 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
.
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 tspanner 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.
π/2angle Yao graphs are spanners.
arXiv: 1001.2913v1 [cs.CG], January 2010.
 WL02

Yu Wang and XiangYang 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 194201, 2002.
 Yao82

A. C. Yao.
On constructing minimum spanning trees in kdimensional spaces and
related problems.
SIAM J. Comput., 11(4):721736, 1982.
Next: Problem 71: StretchFactor for
Up: The Open Problems Project
Previous: Problem 69: Isoceles Planar
The Open Problems Project  September 19, 2017