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, New York, NY, USA , 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.
Repository Staff Only: item control page