On the relation between graph distance and Euclidean distance in random geometric graphs. (English) Zbl 1348.05188

Díaz, J.; Mitsche, D.; Perarnau, G.; Pérez-Giménez, X.

Adv. Appl. Probab. 48, No. 3, 848-864 (2016).

Summary: Given any two vertices \(u\), \(v\) of a random geometric graph \(\mathcal{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=\omega (\sqrt{\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)\).

MSC:

05C80	Random graphs (graph-theoretic aspects)
68R10	Graph theory (including graph drawing) in computer science

Keywords:

random geometric graph; graph distance; Euclidean distance; diameter