Non-existence of annular separators in geometric graphs

DOI10.1007/S00454-023-00519-8MaRDI QIDQ6151030zbMATH OpenOpenAlexFDO

Authors Farzam Ebrahimnejad, James R. Lee

Publication date 9 February 2024

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.09790

zbMATH Keywords

graph separatorspolynomial growthsphere packings

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Abstract: Benjamini and Papasoglou (2011) showed that planar graphs with uniform polynomial volume growth admit $1$-dimensional annular separators: The vertices at graph distance $R$ from any vertex can be separated from those at distance $2R$ by removing at most $O(R)$ vertices. They asked whether geometric $d$-dimensional graphs with uniform polynomial volume growth similarly admit $(d-1)$-dimensional annular separators when $d>2$. We show that this fails in a strong sense: For any $dgeq3$ and every $sgeq1$, there is a collection of interior-disjoint spheres in $mathbb{R}^d$ whose tangency graph $G$ has uniform polynomial growth, but such that all annular separators in $G$ have cardinality at least $R^s$.

Recommendations

• Separators for sphere-packings and nearest neighbor graphs
• Planar Separators
• Annulus graphs in \(\mathbb{R}^d\)
• Sublinear separators in intersection graphs of convex shapes
• Simple polytopes without small separators

Cites work

• A mating-of-trees approach for graph distances in random planar maps
• A Separator Theorem for Planar Graphs
• Combinatorial aspects of geometric graphs
• Geometric Separators for Finite-Element Meshes
• Growth and isoperimetric profile of planar graphs
• Growth and percolation on the uniform infinite planar triangulation
• scientific article; zbMATH DE number 1003278 (Why is no real title available?)
• On planar graphs of uniform polynomial growth
• Quasisymmetric parametrizations of two-dimensional metric spheres
• Recurrence of distributional limits of finite planar graphs
• Separators for sphere-packings and nearest neighbor graphs
• Spectral partitioning works: planar graphs and finite element meshes
• The fractal dimension of Liouville quantum gravity: universality, monotonicity, and bounds
• Uniform Infinite Planar Triangulation and Related Time-Reversed Critical Branching Process

Cited in

(1)

• Annulus graphs in \(\mathbb{R}^d\)

This page was built for publication: Non-existence of annular separators in geometric graphs

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