On the relation between graph distance and Euclidean distance in random geometric graphs

Josep Diaz, Dieter Mitsche, Guillem Perarnau, Xavier Perez-Gimenez

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)
245 Downloads (Pure)

Abstract

Given any two vertices u, v of a random geometric graph G(n, r), denote by dE(u, v) their Euclidean distance and by dE(u, v) their graph distance. The problem of finding upper bounds on dG(u, v) conditional on dE(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=ω(√logn) (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 dE(u, v) conditional on dE(u, v).
Original languageEnglish
Pages (from-to)848-864
Number of pages17
JournalAdvances in Applied Probability
Volume48
Issue number3
DOIs
Publication statusPublished - 19 Sept 2016

Keywords

  • Random geometric graph
  • graph distance
  • Euclidean distance
  • diameter

Fingerprint

Dive into the research topics of 'On the relation between graph distance and Euclidean distance in random geometric graphs'. Together they form a unique fingerprint.

Cite this