ON THE RELATION BETWEEN GRAPH DISTANCE AND EUCLIDEAN DISTANCE IN RANDOM GEOMETRIC GRAPHS

摘要

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(G)(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 = omega(root 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(G)(u, v) conditional on d(E)(u, v).