A Partial Unit Delaunay Graph with Planar and Spanner for Ad Hoc Wireless Networks
This paper proposes a new geometry structure, namely Partial unit Delaunay graph (PuDel), to be as the underlying network topology of Ad hoc wireless networks. PuDel has the following attractive properties: (1) PuDel is a connected subgraph of unit Delaunay triangulation; (2) PuDel is a planar spanner of Unit Disk Graph (UDG) whose length stretch factor is at most 1.21; and (3) PuDel can be locally constructed only based on the position information of 1-hops neighbors, and requires no message exchange between nodes in addition to maintaining UDG.
P. F. Xu et al., "A Partial Unit Delaunay Graph with Planar and Spanner for Ad Hoc Wireless Networks", Advanced Materials Research, Vol. 267, pp. 322-327, 2011