Undirected Connectivity of Sparse Yao Graphs

Details Undirected Connectivity of Sparse Yao Graphs Undirected Connectivity of Sparse Yao Graphs

2011-03-22

arxiv.org/abs/1103.4343v1

Computer Science

Computational Geometry

7 pages, 11 figures

Scientific paper

Given a finite set S of points in the plane and a real value d > 0, the d-radius disk graph G^d contains all edges connecting pairs of points in S that are within distance d of each other. For a given graph G with vertex set S, the Yao subgraph Y_k[G] with integer parameter k > 0 contains, for each point p in S, a shortest edge pq from G (if any) in each of the k sectors defined by k equally-spaced rays with origin p. Motivated by communication issues in mobile networks with directional antennas, we study the connectivity properties of Y_k[G^d], for small values of k and d. In particular, we derive lower and upper bounds on the minimum radius d that renders Y_k[G^d] connected, relative to the unit radius assumed to render G^d connected. We show that d=sqrt(2) is necessary and sufficient for the connectivity of Y_4[G^d]. We also show that, for d <= ~1.056, the graph Y_3[G^d] can be disconnected, but for d >= 2/sqrt(3), Y_3[G^d] is always connected. Finally, we show that Y_2[G^d] can be disconnected, for any d >= 1.

Affiliated with

Also associated with

No associations

Rating

Undirected Connectivity of Sparse Yao Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Undirected Connectivity of Sparse Yao Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Undirected Connectivity of Sparse Yao Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-49600