Strongly sublinear separators and polynomial expansion

DOI10.1137/15M1017569MaRDI QIDQ2808163zbMATH OpenOpenAlexFDO

Authors 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

Connectivity (05C40) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75)

Abstract: A result of Plotkin, Rao, and Smith implies that graphs with polynomial expansion have strongly sublinear separators. We prove a converse of this result showing that hereditary classes of graphs with strongly sublinear separators have polynomial expansion. This confirms a conjecture of the first author.

Recommendations

• A note on sublinear separators and expansion
• Sublinear separators, fragility and subexponential expansion
• Polynomial expansion and sublinear separators
• On classes of graphs with strongly sublinear separators

Cites work

• A separator theorem for graphs of bounded genus
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Characterisations and examples of graph classes with bounded expansion
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Graph minors. II. Algorithmic aspects of tree-width
• Lower bounds for the isoperimetric numbers of random regular graphs
• Sparsity. Graphs, structures, and algorithms
• Sublinear separators, fragility and subexponential expansion
• Treewidth of graphs with balanced separations

Cited in

(32)

• Satisfying subtype inequalities in polynomial space
• Polynomial expansion and sublinear separators
• 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
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Improved bounds for weak coloring numbers
• Treetopes and their graphs
• A note on sublinear separators and expansion
• Two lower bounds for p-centered colorings
• Approximation algorithms for polynomial-expansion and low-density graphs
• Orthogonal tree decompositions of graphs
• Sublinear separators in intersection graphs of convex shapes
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Twin-width II: small classes
• Extremal functions for sparse minors
• Odd colourings, conflict-free colourings and strong colouring numbers
• On weighted sublinear separators
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• Recent progress towards Hadwiger's conjecture
• Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces
• Cop-width, flip-width and strong colouring numbers
• A survey of degree-boundedness
• Twin-width. VIII: Delineation and win-wins
• Bounding the Weisfeiler-Leman dimension via a depth analysis of I/R-trees
• Greedy spanners in Euclidean spaces admit sublinear separators
• Pliability and approximating Max-CSPs
• On the edge crossings of the greedy spanner
• Shallow brambles
• Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
• Sublinear separators, fragility and subexponential expansion

This page was built for publication: Strongly sublinear separators and polynomial expansion

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