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

DOI10.1007/978-3-540-73951-7_27MaRDI QIDQ3603535zbMATHOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(4)

• On a family of strong geometric spanners that admit local routing strategies
• Local routing in spanners based on WSPDs
• Light Euclidean Spanners with Steiner Points
• Local routing in WSPD-based spanners

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)