Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-02-11T15:01:20.695Z Has data issue: false hasContentIssue false
  • English
  • Français

On the treewidth of random geometric graphs and percolated grids

Part of: Equilibrium statistical mechanics Geometric probability and stochastic geometry Graph theory

Published online by Cambridge University Press:  17 March 2017

Anshui Li  and
Tobias Müller
Anshui Li*
Affiliation:
Hangzhou Normal University
Tobias Müller*
Affiliation:
Utrecht University
*
* Postal address: Department of Mathematics, Hangzhou Normal University, Hangzhou, 310000, P.R. China. Email address: anshuili@hznu.edu.cn
** Postal address: Mathematical Institute, Utrecht University, Utrecht, 3508TA, The Netherlands. Email address: t.muller@uu.nl
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we study the treewidth of the random geometric graph, obtained by dropping n points onto the square [0,√n]2 and connecting pairs of points by an edge if their distance is at most r=r(n). We prove a conjecture of Mitsche and Perarnau (2014) stating that, with probability going to 1 as n→∞, the treewidth of the random geometric graph is 𝜣(r√n) when lim inf r>rc, where rc is the critical radius for the appearance of the giant component. The proof makes use of a comparison to standard bond percolation and with a little bit of extra work we are also able to show that, with probability tending to 1 as k→∞, the treewidth of the graph we obtain by retaining each edge of the k×k grid with probability p is 𝜣(k) if p>½ and 𝜣(√log k) if p<½.

Keywords

Random geometric graphtreewidth

MSC classification

Primary: 05C80: Random graphs
Secondary: 60D05: Geometric probability and stochastic geometry 82B43: Percolation
Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 1 , March 2017 , pp. 49 - 60
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Alon, N.,Seymour, P. and Thomas, R. (1990).A separator theorem for nonplanar graphs.J. Amer. Math. Soc. 3,801–808.Google Scholar
[2] Balogh, J. et al. (2011).Hamilton cycles in random geometric graphs.Ann. Appl. Prob. 21,1053–1072.CrossRefGoogle Scholar
[3] Bollobás, B. and Riordan, O. (2006).Percolation.Cambridge University Press.Google Scholar
[4] Cooper, C. and Frieze, A. (2011).The cover time of random geometric graphs.Random Structures Algorithms 38,324–349.Google Scholar
[5] Courcelle, B. (1990).The monadic second-order logic of graphs. I. Recognizable sets of finite graphs.Inf. Comput. 85,12–75.CrossRefGoogle Scholar
[6] Diestel, R. (2010).Graph Theory(Grad. Texts Math. 173),4th edn.Springer,Heidelberg.Google Scholar
[7] Gilbert, E. N. (1961).Random plane networks.J. Soc. Indust. Appl. Math. 9,533–543.Google Scholar
[8] Goel, A.,Rai, S. and Krishnamachari, B. (2005).Monotone properties of random geometric graphs have sharp thresholds.Ann. Appl. Prob. 15,2535–2552.Google Scholar
[9] Grimmett, G. (1999).Percolation(Fundamental Principles Math. Sci. 321),2nd edn.Springer,Berlin.CrossRefGoogle Scholar
[10] Halin, R. (1976). S-functions for graphs.J. Geom. 8,171–186.Google Scholar
[11] Harris, T. E. (1960).A lower bound for the critical probability in a certain percolation process.Proc. Camb. Phil. Soc. 56,13–20.Google Scholar
[12] Kesten, H. (1980).The critical probability of bond percolation on the square lattice equals ½.Commun. Math. Phys. 74,41–59.Google Scholar
[13] Kesten, H. (1981).Analyticity properties and power law estimates of functions in percolation theory.J. Statist. Phys. 25,717–756.Google Scholar
[14] Kloks, T. (1994).Treewidth: Computations and Approximations(Lecture Notes Comput. Sci. 842).Springer,Berlin.Google Scholar
[15] Liggett, T. M.,Schonmann, R. H. and Stacey, A. M. (1997).Domination by product measures.Ann. Prob. 25,71–95.Google Scholar
[16] McDiarmid, C. J. H. (2003).Random channel assignment in the plane.Random Structures Algorithms 22,187–212.Google Scholar
[17] McDiarmid, C. and Müller, T. (2011).On the chromatic number of random geometric graphs.Combinatorica 31,423–488.Google Scholar
[18] Meester, R. and Roy, R. (1996).Continuum Percolation(Camb. Tracts Math. 119).Cambridge University Press.Google Scholar
[19] Mitsche, D. and Perarnau, G. (2012).On the treewidth and related parameters of random geometric graphs.In 29th Internat. Symp. on Theoretical Aspects of Computer Science(LIPIcs. Leibniz Internat. Proc. Inform. 14),pp.408–419.Google Scholar
[20] Müller, T. (2008).Two-point concentration in random geometric graphs.Combinatorica 28,529–545.CrossRefGoogle Scholar
[21] Müller, T.,Pérez-Giménez, X. and Wormald, N. (2011).Disjoint Hamilton cycles in the random geometric graph.J. Graph Theory 68,299–322.CrossRefGoogle Scholar
[22] Penrose, M. D. (1997).The longest edge of the random minimal spanning tree.Ann. Appl. Prob. 7,340–361.Google Scholar
[23] Penrose, M. D. (1999).On k-connectivity for a geometric random graph.Random Structures Algorithms 15,145–164.Google Scholar
[24] Penrose, M. D. (2003).Random Geometric Graphs(Oxford Stud. Prob. 5).Oxford University Press.Google Scholar
[25] Robertson, N. and Seymour, P. (1986).Graph minors. II. Algorithmic aspects of tree-width.J. Algorithms 7,309–322.Google Scholar