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 subgraph G' of G with vertex set V 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 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 γ. If G is the graph consisting of all Delaunay edges of length at most 1, and γ = π/3, we show that a modified version of the algorithm produces a plane subgraph G' of the unit-disk graph which 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.

Additional Metadata
Keywords Bounded degree, Diamond triangulation, Spanner
Persistent URL dx.doi.org/10.1142/S0218195909002861
Journal International Journal of Computational Geometry and Applications
Citation
Bose, P, Smid, M, & Xu, D. (Daming). (2009). Delaunay and diamond triangulations contain spanners of bounded degree. In International Journal of Computational Geometry and Applications (Vol. 19, pp. 119–140). doi:10.1142/S0218195909002861