On Geometric Spanners of Euclidean and Unit Disk Graphs

Ljubomir Perkovic & Iyad A. Kanj
We consider the problem of constructing bounded-degree planar geometric spanners of Euclidean and unit-disk graphs. It is well known that the Delaunay subgraph is a planar geometric spanner with stretch factor $C_{delapprox 2.42$; however, its degree may not be bounded. Our first result is a very simple linear time algorithm for constructing a subgraph of the Delaunay graph with stretch factor $ ho =1+2pi(kcos{frac{pi{k)^{-1$ and degree bounded by $k$, for any integer parameter $kgeq 14$....
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.