EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Recursive Algorithms Preserving Properties in Constrained Geometric Graphs

Sami Nazim Hussein, Sabah Abdullah Tamr

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →