On the 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, v n] 2 . 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) = T( log n log log n ), and for c being sufficiently large, and r = r(n) = c, tw(G) = T(r v 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.
Postprint (author's final draft)