On locally Delaunay geometric graphs

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₁-graph on n vertices, then it has O(n^3/2) edges. (ii) We show that for any n there exist D₁-graphs with n vertices and Ω(n^4/3) edges. (iii) We prove that if G is a D₂-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 $n$ unit circles in the plane is O(n^3/2).The first two results improve the best previously known upper and lower bounds of $O(n^ 5/3 )$ and $\Omega(n)$ respectively (see \cite KL03 ). The third result improves the best previously known upper bound of O(n log n ) ([6]). Finally, our last result improves the best previously known upper bound (for the more general case of not necessarily unit circles) of O(n^3/2 κ(n)) (see [1] ), where κ(n) = (log n ) ^O(α2(n)) and where α(n) is the extremely slowly growing inverse Ackermann's function.

REFERENCES

• 1: Pankaj K. Agarwal , Eran Nevo , János Pach , Rom Pinchasi , Micha Sharir , Shakhar Smorodinsky, Lenses in arrangements of pseudo-circles and their applications, Journal of the ACM (JACM), v.51 n.2, p.139-186, March 2004 [doi>10.1145/972639.972641]
• 2: N. Alon, H. Last, R. Pinchasi and M. Sharir, On the complexity of arrangements of circles in the plane, Discrete Comput. Geom., 26 (2001), 465--492.
• 3: Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
• 4: T. M. Chan, On levels in arrangements of curves, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.219, November 12-14, 2000
• 5: H Edelsbrunner , E Welzl, On the maximal number of edges of many faces in an arrangement, Journal of Combinatorial Theory Series A, v.41 n.2, p.159-166, March 1986 [doi>10.1016/0097-3165(86)90078-6]
• 6: S. Kapoor and X.Y. Li, Proximity structures for geometric graphs, International Journal of Computational Geometry and Applications, (2003), to appear.
• 7: X.Y. Li, G. Calinescu and P.J. Wan, Distributed construction of a planar spanner and routing for ad-hoc wireless networks, in 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). Volume 3. (2002)
• 8: János Pach, Finite point configurations, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 9: J. Pach and P.K. Agarwal, it Combinatorial Geometry, John Wiley & Sons, New York, NY 1995.
• 10: János Pach , Rom Pinchasi , Gábor Tardos , Géza Tóth, Geometric Graphs with No Self-intersecting Path of Length Three, Revised Papers from the 10th International Symposium on Graph Drawing, p.295-311, August 26-28, 2002
• 11: Rom Pinchasi , Radoa Radoicic, Topological graphs with no self-intersecting cycle of length 4, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777807]
• 12: H. Tamaki and T. Tokuyama, How to cut pseudo-parabolas into segments, Discrete Comput. Geom. 19 (1998), 265--290.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

General Terms:
Theory

Keywords:
Delaunay, extremal graph theory, geometric graphs, sensor networks