See Figure 2 (a) for an
illustration. Let disk(u, v) be the disk with diameter uv. Then, the Gabriel
graph [20] GG(G) contains an edge uv from G if and only if disk(u, v) contains
no other vertex w ??? V such that there exist edges uw and wv from G. See
Figure 2 (b) for an illustration. When G is a unit disk graph, we use RNG(V )
and GG(V ) to denote the graphs instead of RNG(G) and GG(G).
Both RNG(V ) and GG(V ) are planar graphs (that is, no two edges
cross each other), which also implies their sparseness: |RNG(V )| ?‰¤ 3n and
|GG(V )| ?‰¤ 3n, where n is the number of vertices. It is easy to show that
RNG(V ) is a subgraph of GG(V ). For an undirected and connected graph
117
Yu Wang
G, both GG(G) and RNG(G) are connected and contain the minimum spanning
tree of G. In other words, if the UDG(V ) is connected, the constructed
RNG(V ) and GG(V ) are connected too. This insures the connectivity of the
sensor networks. Another important property they have is that they can be
constructed easily using localized methods. From the definitions, each node
only needs information from its one-hop neighbors to construct the RNG(V )
and GG(V ).
v u u v w
u
v
(a) RNG (b) GG (c) Del
Fig. 2. The definitions of RNG, GG and Del on a point set. The shaded area is
empty of nodes inside. (a): The lune using uv is empty for RNG. (b): The diametric
circle using uv is empty for GG. (c): The circumcircle of uvw is empty for Del.
Pages:
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203