EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER

Abstract

Given a set V of n points in a two-dimensional plane, we give an O(n log n)-time centralized algorithm that constructs a planar t-spanner for V, for [Formula: see text] such that the degree of each node is bounded from above by [Formula: see text], where 0<α<π/2 is an adjustable parameter. Here C del is the spanning ratio of the Delaunay triangulation, which is at most [Formula: see text]. We also show, by applying the greedy method in Ref. [14], how to construct a low weighted bounded degree planar spanner with spanning ratio ρ(α) 2 (1+∊) and the same degree bound, where ∊ is any positive real constant. Here, a structure is called low weighted if its total edge length is proportional to the total edge length of the Euclidean minimum spanning tree of V. Moreover, we show that our method can be extended to construct a planar bounded degree spanner for unit disk graphs with the adjustable parameter α satisfying 0<α<π/3. Previously, only centralized method 6 of constructing bounded degree planar spanner is known, with degree bound 27 and spanning ratio t≃10.02. The distributed implementation of this centralized method takes O(n 2 ) communications in the worst case. Our method can be converted to a localized algorithm where the total number of messages sent by all nodes is at most O(n).