Strongly Sublinear Separators and Polynomial Expansion
From MaRDI portal
Publication:2808163
DOI10.1137/15M1017569zbMath1336.05073arXiv1504.04821OpenAlexW2962961215MaRDI QIDQ2808163
Publication date: 26 May 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.04821
Structural characterization of families of graphs (05C75) Connectivity (05C40) Density (toughness, etc.) (05C42)
Related Items
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond, Improved bounds for weak coloring numbers, Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, Twin-width II: small classes, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Polynomial expansion and sublinear separators, Two lower bounds for $p$-centered colorings, On weighted sublinear separators, Shallow Minors, Graph Products, and Beyond-Planar Graphs, Treetopes and their graphs, Recent progress towards Hadwiger's conjecture, Unnamed Item, A note on sublinear separators and expansion, Orthogonal Tree Decompositions of Graphs, On classes of graphs with strongly sublinear separators, Packing and covering balls in graphs excluding a minor, Notes on graph product structure theory, Twin-width and generalized coloring numbers, Sublinear Separators in Intersection Graphs of Convex Shapes, Extremal functions for sparse minors
Cites Work
- Sparsity. Graphs, structures, and algorithms
- Characterisations and examples of graph classes with bounded expansion
- Sublinear separators, fragility and subexponential expansion
- Treewidth of graphs with balanced separations
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- A separator theorem for graphs of bounded genus
- Graph minors. II. Algorithmic aspects of tree-width
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- Lower Bounds for the Isoperimetric Numbers of Random Regular Graphs
