On a Family of Strong Geometric Spanners That Admit Local Routing Strategies

DOI10.1007/978-3-540-73951-7_27zbMATH Open1209.68355arXivcs/0702117OpenAlexW1994065834MaRDI QIDQ3603535FDOQ3603535

Authors: Prosenjit Bose, Paz Carmi, M. Couture, Daming Xu, Michiel Smid 

Publication date: 17 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We introduce a family of directed geometric graphs, denoted $paz$, that depend on two parameters $lambda$ and $heta$. For $0leqheta<fracpi2$ and $1/2<lambda<1$, the $paz$ graph is a strong $t$-spanner, with $t=frac1(1-lambda)cosheta$. The out-degree of a node in the $paz$ graph is at most $lfloor2pi/min(heta,arccosfrac12lambda)floor$. Moreover, we show that routing can be achieved locally on $paz$. Next, we show that all strong $t$-spanners are also $t$-spanners of the unit disk graph. Simulations for various values of the parameters $lambda$ and $heta$ indicate that for random point sets, the spanning ratio of $paz$ is better than the proven theoretical bounds.

Full work available at URL: https://arxiv.org/abs/cs/0702117

Recommendations

• On a family of strong geometric spanners that admit local routing strategies
• On the spanning and routing ratios of the directed \(\Theta_6\)-graph
• Local geometric spanners
• On spanners and lightweight spanners of geometric graphs
• On geometric spanners of Euclidean and unit disk graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (2)

• On a family of strong geometric spanners that admit local routing strategies
• Light Euclidean Spanners with Steiner Points

This page was built for publication: On a Family of Strong Geometric Spanners That Admit Local Routing Strategies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3603535)