Arya et al [7, 8] gave a centralized algorithm to construct a spanner with
bounded node degree and the total edge length is no more than a constant
factor of that of MST. However, it is very complicated to transform their
algorithms to a distributed algorithm and their spanners are not planar.
Recently, Bose et al [53] proposed the first centralized algorithm which constructs
a bounded-degree and low-weight planar spanner for a given point set
V . The basic steps of their algorithm is as follows. First, compute the Delaunay
triangulation of V , Del(V ), and a degree-3 spanning subgraph BDS(V )
of Del(V ) that includes the convex hull CH(V ) of V . This graph BDS(V )
partitions CH(V ) into (possibly degenerate) simple polygons, such that each
node of V is on the boundary of at most three polygons. For each polygon P
in the above partition, their algorithm first orders the nodes according to a
geometry based breadth-first search, and processes the nodes of P in increasing
order. It prunes this part of the Delaunay triangulation (edges inside or
on the boundary of P) such that each node of P has low degree. The resulting
graph is a planar spanner for the nodes of P in the sense that any two nodes
u and v of P are connected by a path whose length is at most a constant
times the length of a shortest path between u and v that is completely contained
in P. By combining all the spanners for each of the polygons, they get
a planar spanner of bounded degree.
Pages:
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229