Abstract
Let n be a positive integer, λ> 0 a real number, and 1≤ p≤ ∞. We study the unit disk random geometric graphG p (λ,n), defined to be the random graph on n vertices, independently distributed uniformly in the standard unit disk in \({\mathbb R}^2\), with two vertices adjacent if and only if their ℓ p -distance is at most λ. Let \(\lambda=c\sqrt{\ln n/n}\), and let a p be the ratio of the (Lebesgue) areas of the ℓ p - and ℓ2-unit disks. Almost always, G p (λ,n) has no isolated vertices and is also connected if c>a p − − 1/2, and has \(n^{1-a_pc^2}(1+o(1))\) isolated vertices if c<a p − − 1/2. Furthermore, we find upper bounds (involving λ but independent of p) for the diameter of G p (λ,n), building on a method originally due to M. Penrose.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Chen, X., Jia, X.: Package routing algorithms in mobile ad-hoc wireless networks. In: 2001 International Conference on Parallel Processing Workshops, pp. 485–490 (2001)
Stojmenovic, I., Seddigh, M., Zunic, J.: Dominating sets and neighbor eliminationbased broadcasting algorithms in wireless networks. IEEE Trans. Parallel Distrib. Syst. 13, 14–25 (2002)
Wu, J., Li, H.: A dominating-set-based routing scheme in ad hoc wireless networks. Telecommunication Systems 18, 13–36 (2001)
Ellis, R.B., Jia, X., Yan, C.H.: On random points in the unit disk (preprint)
Whittaker, E.T., Watson, G.N.: A course of modern analysis. Cambridge University Press, Cambridge (1996)
Penrose, M.D.: On k-connectivity for a geometric random graph. Random Structures Algorithms 15, 145–164 (1999)
Alon, N., Spencer, J.H.: The probabilistic method, 2nd edn. John Wiley, Chichester (2000)
Klarner, D.A.: Cell growth problems. Canad. J. Math. 19, 851–863 (1967)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ellis, R.B., Martin, J.L., Yan, C. (2005). Random Geometric Graph Diameter in the Unit Disk with ℓ p Metric. In: Pach, J. (eds) Graph Drawing. GD 2004. Lecture Notes in Computer Science, vol 3383. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31843-9_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-31843-9_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24528-5
Online ISBN: 978-3-540-31843-9
eBook Packages: Computer ScienceComputer Science (R0)