Sublinear separators in intersection graphs of convex shapes

DOI10.1137/20M1311156MaRDI QIDQ4992837zbMATH OpenFDO

Authors Zdeněk Dvořák, Rose McCarty, 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

generalized coloring numbersintersection graphssublinear separators

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)

Abstract: We give a natural sufficient condition for an intersection graph of compact convex sets in R^d to have a balanced separator of sublinear size. This condition generalizes several previous results on sublinear separators in intersection graphs. Furthermore, the argument used to prove the existence of sublinear separators is based on a connection with generalized coloring numbers which has not been previously explored in geometric settings.

Recommendations

• Balanced line separators of unit disk graphs
• Separators in region intersection graphs
• Balanced line separators of unit disk graphs
• Separator theorems and Turán-type results for planar intersection graphs
• 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
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Colouring graphs with bounded generalized colouring number
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Geometric Separators for Finite-Element Meshes
• scientific article; zbMATH DE number 1003278 (Why is no real title available?)
• scientific article; zbMATH DE number 3027510 (Why is no real title available?)
• On classes of graphs with strongly sublinear separators
• On the generalised colouring numbers of graphs that exclude a fixed minor
• Polynomial expansion and sublinear separators
• Separators for sphere-packings and nearest neighbor graphs
• Some Intersection Properties of Convex Bodies
• Strongly sublinear separators and polynomial expansion
• The complexity of the free space for a robot moving amidst fat obstacles
• The intrinsic dimensionality of graphs

Cited in

(13)

• The invariance of weak convexity conditions of \(B\)-nets with respect to subdivision
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Improved bounds for weak coloring numbers
• Balanced line separators of unit disk graphs
• Odd colourings, conflict-free colourings and strong colouring numbers
• Non-existence of annular separators in geometric graphs
• Bounding generalized coloring numbers of planar graphs using coin models
• Asymptotic dimension of intersection graphs
• Product structure of graph classes with strongly sublinear separators
• A survey of degree-boundedness
• Greedy spanners in Euclidean spaces admit sublinear separators
• Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
• Sublinear hitting sets for some geometric graphs

This page was built for publication: Sublinear separators in intersection graphs of convex shapes

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