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 ∈ G(n, r) in [0, √n]². More precisely, let rc denote the threshold radius for the appearance of the giant component in G(n, r). We then show that for any constant 0 < r < rc, tw(G) = Θ(log n/log log n), and for c being sufficiently large, and r = r(n) ≥ c, tw(G) = Θ(r√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. [ABSTRACT FROM AUTHOR]