Random geometric graph diameter in the unit ball

DOI10.1007/S00453-006-0172-YzbMATH Open1117.05099arXivmath/0501214OpenAlexW2162752950MaRDI QIDQ879961FDOQ879961

Authors: Robert B. Ellis, Jeremy L. Martin, Catherine Yan 

Publication date: 10 May 2007

Published in: Algorithmica (Search for Journal in Brave)

Abstract: The unit ball random geometric graph $G=G_p^d(lambda,n)$ has as its vertices $n$ points distributed independently and uniformly in the $d$-dimensional unit ball, with two vertices adjacent if and only if their $l_p$-distance is at most $lambda$. Like its cousin the Erdos-Renyi random graph, $G$ has a connectivity threshold: an asymptotic value for $lambda$ in terms of $n$, above which $G$ is connected and below which $G$ is disconnected (and in fact has isolated vertices in most cases). In the connected zone, we determine upper and lower bounds for the graph diameter of $G$. Specifically, almost always, $dia{m}_p(mathbfB)(1-o(1))/lambdaleqdiam(G)leqdia{m}_p(mathbfB)(1+O((lnlnn/lnn{)}^{1/d}))/lambda$, where $dia{m}_p(mathbfB)$ is the $el{l}_p$-diameter of the unit ball $mathbfB$. We employ a combination of methods from probabilistic combinatorics and stochastic geometry.

Full work available at URL: https://arxiv.org/abs/math/0501214

Recommendations

• Graph Drawing
• On random points in the unit disk
• scientific article; zbMATH DE number 1340281
• On the relation between graph distance and Euclidean distance in random geometric graphs
• Stretch and diameter in random geometric graphs

zbMATH Keywords

Erdős-Renyi random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Combinatorial probability (60C05) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (9)

• Title not available (Why is that?)
• Second-order consensus protocols based on transformed \(d\)-path Laplacians
• Graph Drawing
• Detecting a botnet in a network
• Reconstruction of random geometric graphs: breaking the \(\varOmega (r)\) distortion barrier
• A nonlinear data-driven reduced order model for computational homogenization with physics/pattern-guided sampling
• Stretch and diameter in random geometric graphs
• Diameter and broadcast time of random geometric graphs in arbitrary dimensions
• On random points in the unit disk

This page was built for publication: Random geometric graph diameter in the unit ball

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q879961)