06101511

a

06101511 Kanj, Iyad A. Xia, Ge On certain geometric properties of the Yao-Yao graphs. Lin, Guohui (ed.), Combinatorial optimization and applications. 6th international conference, COCOA 2012, Banff, AB, Canada, August 5--9, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31769-9/pbk). Lecture Notes in Computer Science 7402, 223-233 (2012). 2012 Berlin: Springer EN Yao graphs Yao-Yao graphs unit disk graphs spanners

doi:10.1007/978-3-642-31770-5_20

Summary: We show that, for any constant $\rho > 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 $\rho $. 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.