On the relation between graph distance and Euclidean distance in random geometric graphs. (September 2016) - Díaz, J.; Mitsche, D.; Perarnau, G.; Pérez-Giménez, X.
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 ).