On the treewidth of random geometric graphs and percolated grids

DOI10.1017/APR.2016.78zbMATH Open1428.05284OpenAlexW2595084498MaRDI QIDQ5233158FDOQ5233158

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

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)

zbMATH Keywords

treewidthrandom geometric graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• On the tree-depth and tree-width in heterogeneous random graphs
• On treewidth and related parameters of random geometric graphs
• Topology and geometry of random 2-dimensional hypertrees
• Treewidth of the generalized Kneser graphs
• Treewidth of the \(q\)-Kneser 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
• Convergence theorems for some layout measures on random lattice and random geometric graphs

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)