Strongly Sublinear Separators and Polynomial Expansion

DOI10.1137/15M1017569zbMath1336.05073arXiv1504.04821OpenAlexW2962961215MaRDI QIDQ2808163

Zdeněk Dvořák, Serguei Norine

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

zbMATH Keywords

polynomial expansionsublinear separators

Mathematics Subject Classification ID

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