We consider the problem of computing spanners of Euclidean graphs embedded in the 2-dimensional Euclidean plane. We present an
time algorithm that computes a spanner of a Euclidean graph that is of bounded degree and plane, where
is the number of points in the graph. Both upper bounds on the degree and the stretch factor significantly improve the previous bounds. We extend this algorithm to compute a bounded-degree plane
spanner of a Euclidean graph.
Our results rely on elegant structural and geometric results that we develop. Moreover, our results can be extended to Unit Disk graphs under the local distributed model of computation.