Sublinear Separators in Intersection Graphs of Convex Shapes

DOI10.1137/20M1311156zbMath1465.05046arXiv2001.01552MaRDI QIDQ4992837

Rose McCarty, Zdeněk Dvořák, Serguei Norine

Publication date: 10 June 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

intersection graphssublinear separatorsgeneralized coloring numbers

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

Related Items (4)

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ Improved bounds for weak coloring numbers ⋮ Bounding generalized coloring numbers of planar graphs using coin models ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Colouring graphs with bounded generalized colouring number
• The complexity of the free space for a robot moving amidst fat obstacles
• Polynomial expansion and sublinear separators
• On classes of graphs with strongly sublinear separators
• Strongly Sublinear Separators and Polynomial Expansion
• A separator theorem for graphs of bounded genus
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Separators for sphere-packings and nearest neighbor graphs
• Geometric Separators for Finite-Element Meshes
• Some Intersection Properties of Convex Bodies
• The intrinsic dimensionality of graphs
• On the generalised colouring numbers of graphs that exclude a fixed minor

This page was built for publication: Sublinear Separators in Intersection Graphs of Convex Shapes