Sparse String Graphs and Region Intersection Graphs over Minor-Closed Classes have Linear Expansion
arXiv:2604.0790364.5h-index: 2
AI Analysis
This solves a combinatorial graph theory problem for researchers in discrete mathematics and computational geometry, with applications to graph coloring.
The paper proves that sparse string graphs on a fixed surface and sparse region intersection graphs over proper minor-closed classes have linear expansion, with bounds that are constant-factor optimal.
We prove that sparse string graphs in a fixed surface have linear expansion. We extend this result to the more general setting of sparse region intersection graphs over any proper minor-closed class. The proofs are combinatorial and self-contained, and provide bounds that are within a constant factor of optimal. Applications of our results to graph colouring are presented.