On locally Delaunay geometric graphs Conference Paper uri icon


  • Abstract A geometric graph is a simple graph G=(V, E) with an embedding of the set V in the plane such that the points that represent V are in general position. A geometric graph is said to be k-locally Delaunay (or a D k-graph) if for each edge (u, v)∈ E there is a (Euclidean) disc d that contains u and v but no other vertex of G that is within k hops from u or v. The study of these graphs was recently motivated by topology control for wireless networks [6, 7]. We obtain the following results:(i) We prove that if G is a D 1-graph on n vertices, then it has O (n 3/2) edges.(ii) We show that for any n there exist D 1-graphs with n vertices and Ω (n 4/3) edges.(iii) We prove that if G is a D 2-graph on n vertices, then it has O (n) edges. This bound is worst-case asymptotically tight. As an application of the first result, we show that:(iv) The maximum size of a family of pairwise non-overlapping lenses in an arrangement of …

publication date

  • January 1, 2004