# zbMATH — the first resource for mathematics

$$\pi /2$$-angle Yao graphs are spanners. (English) Zbl 1310.68156
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)
Full Text: