A Gabriel graph was used as a planar subgraph in the face routing protocol
[15,21] and the GPSR routing protocol [14] that guarantee the delivery of the
packet. A relative neighborhood graph was used for e?±cient broadcasting
(minimizing the number of retransmissions) in the one-to-one broadcasting
model in [22]. However, the same analysis by Bose et al [9] implied that the
length stretch factor of RNG(V ) is at most n??’1 and the length stretch factor
of GG(V ) is at most 4?????2n??’4
3 . Recently,Wang et al [23] showed that the length
stretch factor of GG(V ) is precisely ???n ??’ 1 actually. Li et al. [24] first studied
and analyzed the power stretch factors of RNG(V ) and GG(V ). They showed
that the power stretch factor of RNG(V ) is actually n??’1 by constructing an
example, and proved that the power stretch factor of any Gabriel graph is 1.
Therefore, in summary, RNG(V ) is not a power/length spanner, while GG(V )
is a power spanner but not a length spanner. For unicast routing in sensor
networks, a Gabriel graph is power e?±cient when a relative neighborhood
graph is not.
Delaunay Triangulation and Its Relatives
While Gabriel graphs and relative neighborhood graphs are not length spanners,
Delaunay triangulation is a well-known length spanner. Assume that
there are no four vertices of V that are co-circular. A triangulation of V is a
Delaunay triangulation, denoted by Del(V ), if the circumcircle of each of its
triangles does not contain any other vertices of V in its interior.
Pages:
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204