Document Open Access Logo

Odd Yao-Yao Graphs are Not Spanners

Authors Yifei Jin, Jian Li, Wei Zhan

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.49.pdf
  • Filesize: 1.82 MB
  • 15 pages

Document Identifiers

Author Details

Yifei Jin
Jian Li
Wei Zhan

Cite As Get BibTex

Yifei Jin, Jian Li, and Wei Zhan. Odd Yao-Yao Graphs are Not Spanners. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.49

Abstract

It is a long standing open problem whether Yao-Yao graphs YY_{k} are all spanners [Li et al. 2002]. Bauer and Damian [Bauer and Damian, 2012] showed that all YY_{6k} for k >= 6 are spanners. Li and Zhan [Li and Zhan, 2016] generalized their result and proved that all even Yao-Yao graphs YY_{2k} are spanners (for k >= 42). However, their technique cannot be extended to odd Yao-Yao graphs, and whether they are spanners are still elusive. In this paper, we show that, surprisingly, for any integer k >= 1, there exist odd Yao-Yao graph YY_{2k+1} instances, which are not spanners.

Subject Classification

Keywords
  • Odd Yao-Yao Graph
  • Spanner
  • Counterexample

Metrics

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

References

  1. Franz Aurenhammer. Voronoi diagrams - survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR), 23(3):345-405, 1991. 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. Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, André van Renssen, and Sander Verdonschot. On the stretch factor of the Θ₄-graph. In Workshop on Algorithms and Data Structures, pages 109-120. Springer, 2013. Google Scholar
  4. 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
  5. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and David Ilcinkas. Connections between Θ-graphs, Delaunay triangulations, and orthogonal surfaces. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 266-278. Springer, 2010. Google Scholar
  6. 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
  7. Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel Smid, and Norbert Zeh. Approximating geometric bottleneck shortest paths. Computational Geometry, 29(3):233-249, 2004. Google Scholar
  8. Prosenjit Bose, Pat Morin, André van Renssen, and Sander Verdonschot. The Θ₅-graph is a spanner. Computational Geometry, 48(2):108-119, 2015. Google Scholar
  9. Prosenjit Bose, André van Renssen, and Sander Verdonschot. On the spanning ratio of theta-graphs. In Workshop on Algorithms and Data Structures, pages 182-194. Springer, 2013. Google Scholar
  10. 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
  11. Mirela Damian. A simple Yao-Yao-based spanner of bounded degree. arXiv preprint arXiv:0802.4325, 2008. Google Scholar
  12. 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
  13. Mirela Damian and Naresh Nelavalli. Improved bounds on the stretch factor of Y₄. Computational Geometry, 62:14-24, 2017. Google Scholar
  14. Mirela Damian and Kristin Raudonis. Yao graphs span Θ-graphs. In Combinatorial Optimization and Applications, pages 181-194. Springer, 2010. Google Scholar
  15. Nawar M El Molla. Yao spanners for wireless ad hoc networks. Master’s thesis, Villanova University, 2009. Google Scholar
  16. David Eppstein. Spanning trees and spanners. Handbook of computational geometry, pages 425-461, 1999. Google Scholar
  17. David Eppstein. Beta-skeletons have unbounded dilation. Computational Geometry, 23(1):43-52, 2002. Google Scholar
  18. BE Flinchbaugh and LK Jones. Strong connectivity in directional nearest-neighbor graphs. SIAM Journal on Algebraic Discrete Methods, 2(4):461-463, 1981. Google Scholar
  19. K Ruben Gabriel and Robert R Sokal. A new statistical approach to geographic variation analysis. Systematic Biology, 18(3):259-278, 1969. Google Scholar
  20. Matthias Grünewald, Tamás Lukovszki, Christian Schindelhauer, and Klaus Volbert. Distributed maintenance of resource efficient wireless network topologies. In European Conference on Parallel Processing, pages 935-946. Springer, 2002. Google Scholar
  21. 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
  22. 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
  23. Jian Li and Wei Zhan. Almost all even Yao-Yao graphs are spanners. The 24rd Annual European Symposium on Algorithms, 2016. Google Scholar
  24. Xiang-Yang Li. Wireless Ad Hoc and Sensor Networks: Theory and Applications. Cambridge, 6 2008. Google Scholar
  25. 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
  26. 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
  27. Giri Narasimhan and Michiel Smid. Geometric spanner networks. Cambridge University Press, 2007. Google Scholar
  28. Jim Ruppert and Raimund Seidel. Approximating the d-dimensional complete euclidean graph. In Proceedings of the 3rd Canadian Conference on Computational Geometry (CCCG 1991), pages 207-210, 1991. Google Scholar
  29. Jörg-Rüdiger Sack and Jorge Urrutia. Handbook of computational geometry. Elsevier, 1999. Google Scholar
  30. Christian Schindelhauer, Klaus Volbert, and Martin Ziegler. Spanners, weak spanners, and power spanners for wireless networks. In International Symposium on Algorithms and Computation, pages 805-821. Springer, 2004. Google Scholar
  31. Christian Schindelhauer, Klaus Volbert, and Martin Ziegler. Geometric spanners with applications in wireless networks. Computational Geometry, 36(3):197-214, 2007. Google Scholar
  32. Godfried T Toussaint. The relative neighbourhood graph of a finite planar set. Pattern recognition, 12(4):261-268, 1980. Google Scholar
  33. Yu Wang, Xiang-Yang Li, and Ophir Frieder. Distributed spanners with bounded degree for wireless ad hoc networks. International Journal of Foundations of Computer Science, 14(02):183-200, 2003. Google Scholar
  34. 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