On Treewidth and Related Parameters of Random Geometric Graphs

Dieter Mitsche, Guillem Perarnau

Research output: Contribution to journalArticlepeer-review

153 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)1328-1354
JournalSIAM Journal on Discrete Mathematics
Volume31
Issue number2
DOIs
Publication statusPublished - 22 Jun 2017

Fingerprint

Dive into the research topics of 'On Treewidth and Related Parameters of Random Geometric Graphs'. Together they form a unique fingerprint.

Cite this