Recursive Algorithms Preserving Properties in Constrained Geometric Graphs
Jurnal Pendidikan Matematika · 25.08.2025 · 2 (4) · 8
DOI: 10.47134/ppm.v2i4.2048 ↗Kurz gefasst
Fachartikel in der Zeitschrift Jurnal Pendidikan Matematika, online erschienen am 25.08.2025. Verfasst von Sami Nazim Hussein und 1 weiteren Autor:innen. Die Arbeit nennt 18 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Hussein, S. N., & Tamr, S. A. (2025). Recursive Algorithms Preserving Properties in Constrained Geometric Graphs. Jurnal Pendidikan Matematika, 2(4), 8. https://doi.org/10.47134/ppm.v2i4.2048
Vancouver
Hussein SN, Tamr SA. Recursive Algorithms Preserving Properties in Constrained Geometric Graphs. Jurnal Pendidikan Matematika. 2025;2(4):8. doi:10.47134/ppm.v2i4.2048
BibTeX
@article{Hussein2025,
author = {Hussein, Sami Nazim and Tamr, Sabah Abdullah},
title = {Recursive Algorithms Preserving Properties in Constrained Geometric Graphs},
journal = {Jurnal Pendidikan Matematika},
year = {2025},
volume = {2},
number = {4},
pages = {8},
doi = {10.47134/ppm.v2i4.2048}
}
EUVIMED