License
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://drops.dagstuhl.de/opus/volltexte/2012/3428/
Go to the corresponding LIPIcs Volume Portal


Mitsche, Dieter ; Perarnau, Guillem

On the treewidth and related parameters of random geometric graphs

pdf-format:
Document 1.pdf (871 KB)


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 =		{http://dx.doi.org/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


DROPS-Home | Fulltext Search | Imprint Published by LZI