Sharp threshold for embedding balanced spanning trees in random geometric graphs

Source abstract

Consider the random geometric graph $\mathcal{G}(n,r)$ obtained by independently assigning a uniformly random position in $[0,1]^2$ to each of the $n$ vertices of the graph and connecting two vertices by an edge whenever their Euclidean distance is at most $r$. We study the event that $\mathcal{G}(n,r)$ contains a spanning copy of a balanced tree $T$ and obtain sharp thresholds for these events. Our methods provide a polynomial-time algorithm for finding a copy of such trees $T$ above the threshold.