On Treewidth and Related Parameters of Random Geometric Graphs

We give asymptotically exact values for the treewidth ${tw}(G)$ of a random geometric graph $G\in{\mathcal G(n,r)}$ in $[0,\sqrt{n}]^2$. More precisely, let $r_c$ denote the threshold radius for the appearance of the giant component in ${\mathcal G(n,r)}$. We then show that for any constant $0 < r < r_c$, ${tw}(G)=\Theta(\frac{\log n}{\log \log n})$, and for $c$ being sufficiently large, and $r=r(n) \geq c$, ${tw}(G)=\Theta(r \sqrt{n})$. Our proofs show that for the corresponding values of $r$ the same asymptotic bounds also hold for the pathwidth and the treedepth of a random geometric graph.