On the treewidth of random geometric graphs and percolated grids

DOI10.1017/APR.2016.78MaRDI QIDQ5233158zbMATH OpenOpenAlexFDO

Authors Anshui Li, Tobias Müller

Publication date 16 September 2019

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/apr.2016.78

zbMATH Keywords

random geometric graphtreewidth

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Percolation (82B43)

Recommendations

• On treewidth and related parameters of random geometric graphs
• On the treewidth and related parameters of random geometric graphs
• A note on treewidth in random graphs
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• Hyperbolic random graphs: separators and treewidth
• First passage percolation on random geometric graphs and an application to shortest-path trees
• Tree graph inequalities and critical behavior in percolation models
• Random graphs, geometry and asymptotic structure
• Percolation and connectivity in AB random geometric graphs
• Bootstrap percolation on random geometric graphs (extended abstract)

Cites work

• A Separator Theorem for Nonplanar Graphs
• Analyticity properties and power law estimates of functions in percolation theory
• Disjoint Hamilton cycles in the random geometric graph
• Domination by product measures
• Graph minors. II. Algorithmic aspects of tree-width
• Hamilton cycles in random geometric graphs
• scientific article; zbMATH DE number 1340281 (Why is no real title available?)
• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• Monotone properties of random geometric graphs have sharp thresholds
• On the chromatic number of random geometric graphs
• On the treewidth and related parameters of random geometric graphs
• Percolation
• Percolation
• Random channel assignment in the plane
• Random Geometric Graphs
• Random Plane Networks
• S-functions for graphs
• The cover time of random geometric graphs
• The critical probability of bond percolation on the square lattice equals 1/2
• The longest edge of the random minimal spanning tree
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth. Computations and approximations
• Two-point concentration in random geometric graphs

Cited in

(11)

• On the tree-depth and tree-width in heterogeneous random graphs
• Treewidth of the generalized Kneser graphs
• Topology and geometry of random 2-dimensional hypertrees
• Convergence theorems for some layout measures on random lattice and random geometric graphs
• On giant components and treewidth in the layers model
• On the treewidth and related parameters of random geometric graphs
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• A note on treewidth in random graphs
• On treewidth and related parameters of random geometric graphs
• Treewidth of the \(q\)-Kneser graphs
• Treewidth of generalized Hamming graph, bipartite Kneser graph and generalized Petersen graph

This page was built for publication: On the treewidth of random geometric graphs and percolated grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233158)