Recursive Algorithms Preserving Properties in Constrained Geometric Graphs - Hussein, Sami Nazim; Tamr, Sabah Abdullah (Indonesian Journal Publisher, 2025)
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.