On the relation between graph distance and Euclidean distance in random geometric graphs. (September 2016)

• Record Type: Journal Article
• Authors: Díaz, J.; Mitsche, D.; Perarnau, G.; Pérez-Giménez, X.
• Is Part Of: Advances in applied probability. Volume 48:Number 3(2016)
• Page Start: 848
• Page End: 864
• Publication Date: 2016-09
• Subjects: Random geometric graph, -- graph distance, -- Euclidean distance, -- diameter; Primary 05C80, -- Secondary 68R10; Probabilities -- Periodicals; Stochastic models -- Periodicals; Electronic journals; Periodicals; 519.2
• DOI: 10.1017/apr.2016.31
• Languages: English
• ISSNs: 0001-8678

Abstract

Abstract: Given any two vertices u, v of a random geometric graph G( n, r ), denote by d E ( u, v ) their Euclidean distance and by d E ( u, v ) their graph distance. The problem of finding upper bounds on d G ( u, v ) conditional on d E ( u, v ) that hold asymptotically almost surely has received quite a bit of attention in the literature. In this paper we improve the known upper bounds for values of r =ω(√log n ) (that is, for r above the connectivity threshold). Our result also improves the best known estimates on the diameter of random geometric graphs. We also provide a lower bound on d E ( u, v ) conditional on d E ( u, v ).