We show that, for any constant ρ > 1, there exists an integer constant k such that the Yao-Yao graph with parameter k defined on a civilized unit disk graph is a geometric spanner of stretch factor ρ. This improves the results of Wang and Li in several aspects, as described in the paper. We also show that the Yao-Yao graph with parameter k = 4 defined on the complete Euclidean graph is not a spanner and is not plane. This partially answers an open problem posed by Demaine, Mitchell and O'Rourke about the spanner properties of Yao-Yao graphs.
展开▼
