Random Geometric Graph Diameter in the Unit Disk with ℓp Metric (Extended Abstract)

Ellis, Robert and Martin, Jeremy and Yan, Catherine (2004) Random Geometric Graph Diameter in the Unit Disk with ℓp Metric (Extended Abstract). In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 167-172(Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_18).

Full text not available from this repository.


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 R2, with two vertices adjacent if and only if their ℓ p -distance is at most λ. Let λ = c ln n/n, and let ap 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 n1−apc2(1+o(1)) isolated vertices if c<ap–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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_18
Classifications: A General Literature > A.001 Introductory and Survey
URI: http://gdea.informatik.uni-koeln.de/id/eprint/583

Actions (login required)

View Item View Item