Recursive Algorithms Preserving Properties in Constrained Geometric Graphs
DOI:
https://doi.org/10.47134/ppm.v2i4.2048Keywords:
Geometric T-Spanners, Recursive Algorithms, Planarity Constraints, Quadtree Decomposition, Bounded Edge CrossingsAbstract
This article discusses recursive algorithms to construct geometric t-spanners with structural properties such as planarity, unit-disk adjacency, and locally bounded edge crossings. A geometric t-spanner is a sparse subgraph that bounds the distances of the initial geometric graph within a factor t≥1. The suggested recursive approach adopts a three-phase process: (1) Decomposition — the set of vertices is divided into clusters through topological or geometric separators; (2) Local construction — for every cluster, a local spanner is constructed subject to strictly enforcing geometric constraints; and (3) Merging — a sparse set of inter-cluster edges is added in order to link clusters into a global spanner. The model ensures low stretch, bounded degree, and global connectivity at the minimum total number of edges.We demonstrate the scheme through an example of a quadtree-based decomposition where the 2D Euclidean plane is recursively partitioned into subregions that contain a bounded number of vertices. Figures indicate how local spanners and inter-cluster links are combined to form a global structure that closely approximates Euclidean distances and is planar and degree-constrained. The recursive construction is distributable, scalable, and can be used in spatial networks such as wireless sensor systems, road infrastructures, and robotic motion.
References
Bhore, S., Filtser, A., Khodabandeh, H., & Tóth, C. D. (2022). Online spanners in metric spaces. In 30th Annual European Symposium on Algorithms (ESA 2022) (Vol. 244, pp. 1–15). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022
Bhore, S., Filtser, A., Khodabandeh, H., & Tóth, C. D. (2024). Online spanners in metric spaces. SIAM Journal on Discrete Mathematics, 38(1), 1030–1056. https://doi.org/10.1137/22M1481234
Bhore, S., & Tóth, C. D. (2021). Online Euclidean spanners. In P. Mutzel, R. Pagh, & G. Herman (Eds.), 29th Annual European Symposium on Algorithms (ESA 2021) (Vol. 204, pp. 16:1–16:19). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2021.16
Borradaile, G., Le, H., & Wulff-Nilsen, C. (2019). Greedy spanners are optimal in doubling metrics. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019) (pp. 2371–2379). SIAM. https://doi.org/10.1137/1.9781611975482.144
Bose, P., Carmi, P., Farshi, M., Maheshwari, A., & Smid, M. (2010). Computing the greedy spanner in near-quadratic time. Algorithmica, 58(3), 711–729. https://doi.org/10.1007/s00453-009-9291-5
Bose, P., Gudmundsson, J., & Morin, P. (2004). Ordered theta graphs. Computational Geometry, 28(1), 11–18. https://doi.org/10.1016/j.comgeo.2004.02.001
Braynard, R., Kostic, D., Rodriguez, A., Chase, J., & Vahdat, A. (2002). Opus: An overlay peer utility service. In Proceedings of the 5th IEEE Conference on Open Architectures and Network Programming (OPENARCH) (pp. 167–178). IEEE. https://doi.org/10.1109/OPENAR.2002.1016721
Chan, T.-H. H., & Gupta, A. (2009). Small hop-diameter sparse spanners for doubling metrics. Discrete & Computational Geometry, 41(1), 28–44. https://doi.org/10.1007/s00454-008-9105-6
Chan, T. M., & Skrepetos, D. (2019). Approximate shortest paths and distance oracles in weighted unit-disk graphs. Journal of Computational Geometry, 10(2), 3–20. https://doi.org/10.20382/jocg.v10i2a2
Chechik, S., Langberg, M., Peleg, D., & Roditty, L. (2010). Fault tolerant spanners for general graphs. SIAM Journal on Computing, 39(7), 3403–3423. https://doi.org/10.1137/090749145
Chew, P. (1986). There is a planar graph almost as good as the complete graph. In Proceedings of the Second Annual Symposium on Computational Geometry (pp. 169–177). ACM. https://doi.org/10.1145/10515.10534
Chew, P. (1989). There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences, 39(2), 205–219. https://doi.org/10.1016/0022-0000(89)90044-5
Choudhary, P., Goodrich, M. T., Gupta, S., Khodabandeh, H., Matias, P., & Raman, V. (2023). Improved kernels for tracking paths. Information Processing Letters, 181, 106360. https://doi.org/10.1016/j.ipl.2022.106360
Dobson, A., & Bekris, K. E. (2014). Sparse roadmap spanners for asymptotically near-optimal motion planning. International Journal of Robotics Research, 33(1), 18–47. https://doi.org/10.1177/0278364913498294
Dujmović, V., Eppstein, D., & Wood, D. R. (2017). Structure of graphs with locally restricted crossings. SIAM Journal on Discrete Mathematics, 31(2), 805–824. https://doi.org/10.1137/16M1062879
Dvorak, Z., & Norin, S. (2016). Strongly sublinear separators and polynomial expansion. SIAM Journal on Discrete Mathematics, 30(2), 1095–1101. https://doi.org/10.1137/15M1036144
Elkin, M. (2005). Computing almost shortest paths. ACM Transactions on Algorithms, 1(2), 283–323. https://doi.org/10.1145/1103963.1103968
Elkin, M., Filtser, A., & Neiman, O. (2020). Distributed construction of light networks. In Proceedings of the 39th Symposium on Principles of Distributed Computing (pp. 483–492). ACM. https://doi.org/10.1145/3382734.3405725
Downloads
Published
How to Cite
Issue
Section
