Document Open Access Logo

Almost All Even Yao-Yao Graphs Are Spanners

Authors Jian Li, Wei Zhan

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.62.pdf
  • Filesize: 0.61 MB
  • 13 pages

Document Identifiers

Author Details

Jian Li
Wei Zhan

Cite As Get BibTex

Jian Li and Wei Zhan. Almost All Even Yao-Yao Graphs Are Spanners. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 62:1-62:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.62

Abstract

It is an open problem whether Yao-Yao graphs YY_{k} (also known as sparse-Yao graphs) are all spanners when the integer parameter k is large enough. In this paper we show that, for any integer k >= 42, the Yao-Yao graph YY_{2k} is a t_k-spanner, with stretch factor t_k = 6.03+O(k^{-1}) when k tends to infinity. Our result generalizes the best known result which asserts that all YY_{6k} are spanners for k >= 6 [Bauer and Damian, SODA'13]. Our proof is also somewhat simpler.

Subject Classification

Keywords
  • Yao-Yao graph
  • geometric spanner
  • curved trapezoid

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Mirela Damian, Rolf Fagerberg, André van Renssen, Perouz Taslakian, and Sander Verdonschot. Continuous Yao graphs. In Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014, Halifax, Nova Scotia, Canada, 2014, 2014. Google Scholar
  2. Luis Barba, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O'Rourke, André van Renssen, Perouz Taslakian, Sander Verdonschot, and Ge Xia. New and improved spanning ratios for Yao graphs. JoCG, 6(2):19-53, 2015. Google Scholar
  3. Matthew Bauer and Mirela Damian. An infinite class of sparse-Yao spanners. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 184-196. SIAM, 2013. Google Scholar
  4. Prosenjit Bose, Paz Carmi, Sebastien Collette, and Michiel Smid. On the stretch factor of convex delaunay graphs. Journal of computational geometry, 1(1):41-56, 2010. Google Scholar
  5. Prosenjit Bose, Mirela Damian, Karim Douïeb, Joseph O'rourke, Ben Seamone, Michiel Smid, and Stefanie Wuhrer. π/2-angle Yao graphs are spanners. International Journal of Computational Geometry &Applications, 22(01):61-82, 2012. Google Scholar
  6. Prosenjit Bose, Joachim Gudmundsson, and Michiel H. M. Smid. Constructing plane spanners of bounded degree and low weight. Algorithmica, 42(3-4):249-264, 2005. Google Scholar
  7. Paul Chew. There is a planar graph almost as good as the complete graph. In Proceedings of the second annual symposium on Computational geometry, pages 169-177. ACM, 1986. Google Scholar
  8. Artur Czumaj and Hairong Zhao. Fault-tolerant geometric spanners. Discrete &Computational Geometry, 32(2):207-230, 2004. Google Scholar
  9. Mirela Damian. A simple Yao-Yao-based spanner of bounded degree. arXiv preprint arXiv:0802.4325, 2008. Google Scholar
  10. Mirela Damian, Nawar Molla, and Val Pinciu. Spanner properties of π/2-angle Yao graphs. In Proc. of the 25th European Workshop on Computational Geometry, pages 21-24. Citeseer, 2009. Google Scholar
  11. Mirela Damian and Kristin Raudonis. Yao graphs span theta graphs. In Combinatorial Optimization and Applications, pages 181-194. Springer, 2010. Google Scholar
  12. David P Dobkin, Steven J Friedman, and Kenneth J Supowit. Delaunay graphs are almost as good as complete graphs. In Foundations of Computer Science, 1987., 28th Annual Symposium on, pages 20-26. IEEE, 1987. Google Scholar
  13. Nawar M El Molla. Yao spanners for wireless ad hoc networks. Master’s thesis, Villanova University, 2009. Google Scholar
  14. Lujun Jia, Rajmohan Rajaraman, and Christian Scheideler. On local algorithms for topology control and routing in ad hoc networks. In Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, pages 220-229. ACM, 2003. Google Scholar
  15. Iyad A Kanj and Ge Xia. On certain geometric properties of the Yao-Yao graphs. In Combinatorial Optimization and Applications, pages 223-233. Springer, 2012. Google Scholar
  16. Xiang-Yang Li. Wireless Ad Hoc and Sensor Networks: Theory and Applications. Cambridge, 6 2008. Google Scholar
  17. Xiang-Yang Li, Peng-Jun Wan, and Yu Wang. Power efficient and sparse spanner for wireless ad hoc networks. In Computer Communications and Networks, 2001. Proceedings. Tenth International Conference on, pages 564-567. IEEE, 2001. Google Scholar
  18. Xiang-Yang Li, Peng-Jun Wan, Yu Wang, and Ophir Frieder. Sparse power efficient topology for wireless networks. In System Sciences, 2002. HICSS. Proceedings of the 35th Annual Hawaii International Conference on, pages 3839-3848. IEEE, 2002. Google Scholar
  19. Xiang-Yang Li and Yu Wang. Efficient construction of low weight bounded degree planar spanner. In Computing and Combinatorics, pages 374-384. Springer, 2003. Google Scholar
  20. Giri Narasimhan and Michiel Smid. Geometric spanner networks. Cambridge University Press, 2007. Google Scholar
  21. David Peleg and Alejandro A Schäffer. Graph spanners. Journal of graph theory, 13(1):99-116, 1989. Google Scholar
  22. Christian Schindelhauer, Klaus Volbert, and Martin Ziegler. Geometric spanners with applications in wireless networks. Computational Geometry, 36(3):197-214, 2007. Google Scholar
  23. Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721-736, 1982. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact