Polynomial expansion and sublinear separators

DOI10.1016/j.ejc.2017.09.003zbMath1376.05077arXiv1705.01438OpenAlexW2611328153MaRDI QIDQ1686248

Jean-Florent Raymond, Louis Esperet

Publication date: 21 December 2017

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

polynomial expansionsublinear separators

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)

Related Items (8)

Improved bounds for weak coloring numbers ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ On weighted sublinear separators ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Sparse graphs without long induced paths ⋮ A note on sublinear separators and expansion ⋮ Notes on graph product structure theory ⋮ Sublinear Separators in Intersection Graphs of Convex Shapes

Cites Work

• Unnamed Item
• Small complete minors above the extremal edge density
• Sparsity. Graphs, structures, and algorithms
• Strongly Sublinear Separators and Polynomial Expansion
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Degree-3 Treewidth Sparsifiers
• Large-treewidth graph decompositions and applications

This page was built for publication: Polynomial expansion and sublinear separators