Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T17:43:04.908Z 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: [email protected]
** Postal address: Mathematical Institute, Utrecht University, Utrecht, 3508TA, The Netherlands. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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