Given a triangulation G, whose vertex set V is a set of n points in the plane, and given a real number γ with 0<γ<π, we design an O(n)-time algorithm that constructs a connected spanning subgraph G′ of G whose maximum degree is at most 14+[2π/γ]. If G is the Delaunay triangulation of V, and γ= 2π/3, we show that G′ is a t-spanner of V (for some constant t) with maximum degree at most 17, thereby improving the previously best known degree bound of 23. If G is the graph consisting of all Delaunay edges of length at most 1, and γ= π/3, we show that G′ is a t-spanner (for some constant t) of the unit-disk graph of V, whose maximum degree is at most 20, thereby improving the previously best known degree bound of 25. Finally, if G is a triangulation satisfying the diamond property, then for a specific range of values of γ dependent on the angle of the diamonds, we show that G′ is a t-spanner of V (for some constant t) whose maximum degree is bounded by a constant dependent on γ.

Additional Metadata
Persistent URL dx.doi.org/10.1007/11940128_19
Citation
Bose, P, Smid, M, & Xu, D. (Daming). (2006). Diamond triangulations contain spanners of bounded degree. doi:10.1007/11940128_19