Hostname: page-component-7b7567c8c-lpg2g Total loading time: 0 Render date: 2026-11-15T13:12:26.601Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of:Graph theoryDiscrete mathematics in relation to computer science

Published online by Cambridge University Press:  19 September 2016

J. Díaz,
D. Mitsche,
G. Perarnau and
X. Pérez-Giménez
J. Díaz*
Affiliation:
Universitat Politècnica de Catalunya and BGSMath
D. Mitsche*
Affiliation:
Université Nice Sophia Antipolis
G. Perarnau*
Affiliation:
Universitat Politècnica de Catalunya
X. Pérez-Giménez*
Affiliation:
University of Waterloo
*
* Postal address: Department of Computer Science, Universitat Politècnica de Catalunya, Jordi Girona Salgado 1, 08034 Barcelona, Spain. Email address: diaz@lsi.upc.edu
** Postal address: Laboratoire J. A. Dieudonné, Université Nice Sophia Antipolis, Parc Valrose, 06108 Nice cedex 02, France. Email address: dmitsche@unice.fr
*** Postal address: Department de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Jordi Girona Salgado 1, 08034 Barcelona, Spain. Email address: guillem.perarnau@ma4.upc.edu
**** Postal address: Department of Combinatorics and Optimization, University of Waterloo, Waterloo ON, N2L 3G1, Canada. Email address: xperez@uwaterloo.ca
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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=ω(√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 d E (u, v) conditional on d E (u, v).

Keywords

Random geometric graphgraph distanceEuclidean distancediameter

MSC classification

Primary:05C80: Random graphs
Secondary:68R10: Graph theory (including graph drawing)

Information

Type
Research Article
Information
Advances in Applied Probability , Volume 48 , Issue 3 , September 2016, pp. 848 - 864
Copyright
Copyright © Applied Probability Trust 2016 

References

[1] Bradonjić, M. et al. (2010).Efficient broadcast on random geometric graphs. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms,SIAM,Philadelphia, PA, pp. 1412–1421.Google Scholar
[2] Ellis, R. B.,Martin, J. L. and Yan, C. (2007).Random geometric graph diameter in the unit ball.Algorithmica 47,421–438.Google Scholar
[3] Gilbert, E. N. (1961) Random plane networks.J. Soc. Indust. Appl. Math. 9,533–543.CrossRefGoogle Scholar
[4] Friedrich, T.,Sauerwald, T. and Stauffer, A. (2011).Diameter and broadcast time of random geometric graphs in arbitrary dimensions. In Algorithms and Computation,Springer,Heidelberg, pp. 190–199.Google Scholar
[5] Goel, A.,Rai, S. and Krishnamachari, B. (2004).Sharp thresholds for monotone properties in random geometric graphs. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing,ACM,New York, pp. 580–586.Google Scholar
[6] Mehrabian, A. and Wormald, N. (2013).On the stretch factor of randomly embedded random graphs.Discrete Comput. Geom. 49,647–658.Google Scholar
[7] Muthukrishnan, S. and Pandurangan, G. (2005).The bin-covering technique for thresholding random geometric graph properties. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms,ACM,New York, pp. 989–998.Google Scholar
[8] Penrose, D. M. (1997).The longest edge of the random minimal spanning tree.Ann. Appl. Prob. 7,340–361.CrossRefGoogle Scholar
[9] Penrose, M. (2003).Random Geometric Graphs.Oxford University Press.Google Scholar
[10] Walters, M. (2011).Random geometric graphs. In Surveys in Combinatorics, 2011,Cambridge University Press, pp. 365–401.CrossRefGoogle Scholar