Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs

2025/04/01 by Davies, James, Georgakopoulos, Agelos, Hatzel, Meike +1 · 3 citations
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.2504.00932

Abstract

In this paper, we consider the class C^d of sphere intersection graphs in ℝ^d for d ≥ 2. We show that for each integer t, the class of all graphs in C^d that exclude K_t,t as a subgraph has strongly sublinear separators. We also prove that C^d has asymptotic dimension at most 2d+2.

Cited by

• Nerve-type and invariance theorems for asymptotic dimension
• String graphs are quasi-isometric to planar graphs
• Burling graphs in graphs with large chromatic number

Related

• Sublinear separators in intersection graphs of convex shapes
• Asymptotic dimension of intersection graphs
• Surfaces have (asymptotic) dimension 2
• On classes of graphs with strongly sublinear separators
• Nerve-type and invariance theorems for asymptotic dimension