Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.408
URN: urn:nbn:de:0030-drops-34280
URL: https://drops.dagstuhl.de/opus/volltexte/2012/3428/
Mitsche, Dieter ; Perarnau, Guillem
On the treewidth and related parameters of random geometric graphs
| pdf-format: |
|
Abstract
We give asymptotically exact values for the treewidth tw(G) of a random geometric graph G(n,r) in [0,sqrt(n)]^2. More precisely, we show that there exists some c_1 > 0, such that for any constant 0 < r < c_1, tw(G)=Theta(log(n)/loglog(n)), and also, there exists somec_2 > c_1, such that for any r=r(n)> c_2, 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 treedepth of a random geometric graph.
BibTeX - Entry
@InProceedings{mitsche_et_al:LIPIcs:2012:3428,
author = {Dieter Mitsche and Guillem Perarnau},
title = {{On the treewidth and related parameters of random geometric graphs}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {408--419},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-35-4},
ISSN = {1868-8969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3428},
URN = {urn:nbn:de:0030-drops-34280},
doi = {10.4230/LIPIcs.STACS.2012.408},
annote = {Keywords: Random geometric graphs, treewidth, treedepth}
}
| Keywords: | Random geometric graphs, treewidth, treedepth | |
| Seminar: | 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) | |
| Issue date: | 2012 | |
| Date of publication: | 24.02.2012 |
