Document Open Access Logo

On the Edge Crossings of the Greedy Spanner

Authors David Eppstein, Hadi Khodabandeh

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.33.pdf
  • Filesize: 0.75 MB
  • 17 pages

Document Identifiers

Author Details

David Eppstein
  • Department of Computer Science, University of California, Irvine, CA, USA
Hadi Khodabandeh
  • Department of Computer Science, University of California, Irvine, CA, USA

Funding

This work was supported in part by the US National Science Foundation under grant CCF-1616248.

Cite AsGet BibTex

David Eppstein and Hadi Khodabandeh. On the Edge Crossings of the Greedy Spanner. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.33

Abstract

The greedy t-spanner of a set of points in the plane is an undirected graph constructed by considering pairs of points in order by distance, and connecting a pair by an edge when there does not already exist a path connecting that pair with length at most t times the Euclidean distance. We prove that, for any t > 1, these graphs have at most a linear number of crossings, and more strongly that the intersection graph of edges in a greedy t-spanner has bounded degeneracy. As a consequence, we prove a separator theorem for greedy spanners: any k-vertex subgraph of a greedy spanner can be partitioned into sub-subgraphs of size a constant fraction smaller, by the removal of O(√k) vertices. A recursive separator hierarchy for these graphs can be constructed from their planarizations in linear time, or in near-linear time if the planarization is unknown.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
  • Theory of computation → Computational geometry
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Geometric Spanners
  • Greedy Spanners
  • Separators
  • Crossing Graph
  • Sparsity

Metrics

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

Related Versions

References

  1. Mohammad A Abam and Sariel Har-Peled. New constructions of sspds and their applications. Computational Geometry, 45(5-6):200-214, 2012. Google Scholar
  2. Mohammad Ali Abam, Mark De Berg, Mohammad Farshi, and Joachim Gudmundsson. Region-fault tolerant geometric spanners. Discrete & Computational Geometry, 41(4):556-582, 2009. URL: https://doi.org/10.1007/s00454-009-9137-7.
  3. Ingo Althöfer, Gautam Das, David Dobkin, and Deborah Joseph. Generating sparse spanners for weighted graphs. In John R. Gilbert and Rolf Karlsson, editors, Proceedings of the 2nd Scandinavian Workshop on Algorithm Theory (SWAT), volume 447 of Lecture Notes in Computer Science, pages 26-37. Springer, 1990. URL: https://doi.org/10.1007/3-540-52846-6_75.
  4. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9(1):81-100, 1993. URL: https://doi.org/10.1007/BF02189308.
  5. Khaled Alzoubi, Xiang-Yang Li, Yu Wang, Peng-Jun Wan, and Ophir Frieder. Geometric spanners for wireless ad hoc networks. IEEE Transactions on Parallel and Distributed Systems, 14(4):408-421, 2003. URL: https://doi.org/10.1109/TPDS.2003.1195412.
  6. Srinivasa Arikati, Danny Z. Chen, L. Paul Chew, Gautam Das, Michiel Smid, and Christos D. Zaroliagis. Planar spanners and approximate shortest path queries among obstacles in the plane. In Josep Diaz and Maria Serna, editors, Proceedings of the 4th European Symposium on Algorithms (ESA), volume 1136 of Lecture Notes in Computer Science, pages 514-528. Springer, 1996. URL: https://doi.org/10.1007/3-540-61680-2_79.
  7. Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Near-linear time construction of sparse neighborhood covers. SIAM Journal on Computing, 28(1):263-277, 1998. URL: https://doi.org/10.1137/S0097539794271898.
  8. Sang Won Bae, Jean-Francois Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok-Hee Hong, Matias Korman, Fabrizio Montecchiani, Ignaz Rutter, and Csaba D. Tóth. Gap-planar graphs. Theoretical Computer Science, 745:36-52, 2018. URL: https://doi.org/10.1016/j.tcs.2018.05.029.
  9. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners and (α,β)-spanners. ACM Transactions on Algorithms, 7(1):5, 2010. URL: https://doi.org/10.1145/1868237.1868242.
  10. Glencora Borradaile, Hung Le, and Christian Wulff-Nilsen. Greedy spanners are optimal in doubling metrics. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2371-2379. Society for Industrial and Applied Mathematics, 2019. URL: https://doi.org/10.1137/1.9781611975482.145.
  11. Prosenjit Bose, Paz Carmi, Mohammad Farshi, Anil Maheshwari, and Michiel Smid. Computing the greedy spanner in near-quadratic time. Algorithmica, 58(3):711-729, 2010. URL: https://doi.org/10.1007/s00453-009-9293-4.
  12. Rebecca Braynard, Dejan Kostic, Adolfo Rodriguez, Jeffrey Chase, and Amin Vahdat. Opus: an overlay peer utility service. In Proceedings of the 5th IEEE Conference on Open Architectures and Network Programming (OPENARCH), pages 167-178. IEEE, 2002. URL: https://doi.org/10.1109/OPNARC.2002.1019237.
  13. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. Fault tolerant spanners for general graphs. SIAM Journal on Computing, 39(7):3403-3423, 2010. URL: https://doi.org/10.1137/090758039.
  14. Paul Chew. There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences, 39(2):205-219, 1989. URL: https://doi.org/10.1016/0022-0000(89)90044-5.
  15. Edith Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing, 28(1):210-236, 1998. URL: https://doi.org/10.1137/S0097539794261295.
  16. Gautam Das. The visibility graph contains a bounded-degree spanner. In Proceedings of the 9th Canadian Conference on Computational Geometry (CCCG), pages 70-75, 1997. URL: https://cccg.ca/proceedings/1997/.
  17. Gautam Das and Deborah Joseph. Which triangulations approximate the complete graph? In Hristo Djidjev, editor, Proceedings of the International Symposium on Optimal Algorithms (OA), volume 401 of Lecture Notes in Computer Science, pages 168-192. Springer, 1989. URL: https://doi.org/10.1007/3-540-51859-2_15.
  18. Gautam Das and Giri Narasimhan. A fast algorithm for constructing sparse Euclidean spanners. International Journal of Computational Geometry & Applications, 7(04):297-315, 1997. URL: https://doi.org/10.1142/S0218195997000193.
  19. Andrew Dobson and Kostas E. Bekris. Sparse roadmap spanners for asymptotically near-optimal motion planning. International Journal of Robotics Research, 33(1):18-47, 2014. URL: https://doi.org/10.1177/0278364913498292.
  20. Vida Dujmović, David Eppstein, and David R. Wood. Structure of graphs with locally restricted crossings. SIAM Journal on Discrete Mathematics, 31(2):805-824, 2017. URL: https://doi.org/10.1137/16M1062879.
  21. Zdenek Dvorak and Sergey Norin. Strongly sublinear separators and polynomial expansion. SIAM Journal on Discrete Mathematics, 30(2):1095-1101, 2016. URL: https://doi.org/10.1137/15M1017569.
  22. Michael Elkin. Computing almost shortest paths. ACM Transactions on Algorithms, 1(2):283-323, 2005. URL: https://doi.org/10.1145/1103963.1103968.
  23. Michael Elkin and David Peleg. (1+ε,β)-spanner constructions for general graphs. SIAM Journal on Computing, 33(3):608-631, 2004. URL: https://doi.org/10.1137/S0097539701393384.
  24. Michael Elkin and Jian Zhang. Efficient algorithms for constructing (1+ε,β)-spanners in the distributed and streaming models. Distributed Computing, 18(5):375-385, 2006. URL: https://doi.org/10.1007/s00446-005-0147-2.
  25. David Eppstein. Spanning trees and spanners. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 425-461. North-Holland, 2000. URL: https://doi.org/10.1016/B978-044482537-7/50010-3.
  26. David Eppstein and Michael T. Goodrich. Studying (non-planar) road networks through an algorithmic lens. In Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages A16:1-A16:10. ACM, 2008. URL: https://doi.org/10.1145/1463434.1463455.
  27. David Eppstein, Michael T. Goodrich, and Darren Strash. Linear-time algorithms for geometric graphs with sublinearly many edge crossings. SIAM Journal on Computing, 39(8):3814-3829, 2010. URL: https://doi.org/10.1137/090759112.
  28. David Eppstein and Siddharth Gupta. Crossing patterns in nonplanar road networks. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages A40:1-A40:9. ACM, 2017. URL: https://doi.org/10.1145/3139958.3139999.
  29. Mohammad Farshi and Joachim Gudmundsson. Experimental study of geometric t-spanners. ACM Journal of Experimental Algorithmics, 14:1.3:1-1.3:29, 2009. URL: https://doi.org/10.1145/1498698.1564499.
  30. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the streaming model: the value of space. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 745-754. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  31. Arnold Filtser and Shay Solomon. The greedy spanner is existentially optimal. In Proceedings of the 35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 9-17. ACM, 2016. URL: https://doi.org/10.1145/2933057.2933114.
  32. Alan M. Frieze, Gary L. Miller, and Shang-Hua Teng. Separator based parallel divide and conquer in computational geometry. In Proceedings of the 4th ACM Symposium on Parallel Algorithms and Architectures (SPAA), volume 92, pages 420-429, 1992. URL: https://doi.org/10.1145/140901.141934.
  33. Martin Fürer and Shiva Prasad Kasiviswanathan. Spanners for geometric intersection graphs. In Workshop on Algorithms and Data Structures, pages 312-324. Springer, 2007. Google Scholar
  34. Michael T. Goodrich. Planar separators and parallel polygon triangulation. Journal of Computer and System Sciences, 51(3):374-389, 1995. URL: https://doi.org/10.1006/jcss.1995.1076.
  35. Lee-Ad Gottlieb. A light metric spanner. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 759-772. IEEE, 2015. URL: https://doi.org/10.1109/FOCS.2015.52.
  36. Joachim Gudmundsson, Christos Levcopoulos, and Giri Narasimhan. Fast greedy algorithms for constructing sparse geometric spanners. SIAM Journal on Computing, 31(5):1479-1500, 2002. URL: https://doi.org/10.1137/S0097539700382947.
  37. Lujun Jia, Rajmohan Rajaraman, and Christian Scheideler. On local algorithms for topology control and routing in ad hoc networks. In Proceedings of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 220-229. ACM, 2003. URL: https://doi.org/10.1145/777412.777447.
  38. J. Mark Keil. Approximating the complete Euclidean graph. In Rolf Karlsson and Andrzej Lingas, editors, Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (SWAT), volume 318 of Lecture Notes in Computer Science, pages 208-213. Springer, 1988. URL: https://doi.org/10.1007/3-540-19487-8_23.
  39. David Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28-35, 1983. URL: https://doi.org/10.1137/0212002.
  40. Philip N. Klein, Shay Mozes, and Christian Sommer. Structured recursive separator decompositions for planar graphs in linear time. In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC), pages 505-514. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488672.
  41. Hung Le and Shay Solomon. Truly optimal Euclidean spanners. In Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1078-1100. IEEE, 2019. URL: https://doi.org/10.1109/FOCS.2019.00069.
  42. Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. URL: https://doi.org/10.1137/0136016.
  43. James D. Marble and Kostas E. Bekris. Asymptotically near-optimal planning with probabilistic roadmap spanners. IEEE Transactions on Robotics, 29(2):432-444, 2013. URL: https://doi.org/10.1109/TRO.2012.2234312.
  44. Giri Narasimhan and Michiel Smid. Geometric Spanner Networks. Cambridge University Press, 2007. URL: https://doi.org/10.1017/CBO9780511546884.
  45. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: https://doi.org/10.1002/jgt.3190130114.
  46. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389-401, 2011. URL: https://doi.org/10.1007/s00453-010-9401-5.
  47. Wenjie Wang, Cheng Jin, and Sugih Jamin. Network overlay construction under limited end-to-end reachability. In Proceedings of the 24th Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), volume 3, pages 2124-2134. IEEE, 2005. 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 Imprint Privacy Contact