License: 
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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3428/
Mitsche, Dieter ;
Perarnau, Guillem
On the treewidth and related parameters of random geometric graphs
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 some
c_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 |
|
Collection: |
|
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) |
|
Issue Date: |
|
2012 |
|
Date of publication: |
|
24.02.2012 |
