\(\pi /2\)-angle Yao graphs are spanners. (English) Zbl 1310.68156

Bose, Prosenjit; Damian, Mirela; Douïeb, Karim; O’Rourke, Joseph; Seamone, Ben; Smid, Michiel; Wuhrer, Stefanie

Cheong, Otfried (ed.) et al., Algorithms and computation. 21st international symposium, ISAAC 2010, Jeju, Korea, December 15–17, 2010. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-17513-8/pbk). Lecture Notes in Computer Science 6507, 446-457 (2010).

Summary: We show that the Yao graph \(Y _{4}\) in the \(L _{2}\) metric is a spanner with stretch factor \(8\sqrt{2}(29+23\sqrt{2})\).
For the entire collection see [Zbl 1202.68003].

MSC:

68R10	Graph theory (including graph drawing) in computer science
05C12	Distance in graphs
68U05	Computer graphics; computational geometry (digital and algorithmic aspects)