Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs
Abstract
String graphs are intersection graphs of continuous curves in the plane. In 2010, Fox and Pach proved that string graphs with m edges admit balanced vertex separators of size 𝒪(m3/4√(log m)) and conjectured that this bound can be improved to 𝒪(√m), which would be optimal. After partial progress, Lee claimed in 2017 to prove this conjecture, and more generally to prove analogous separator theorems for region intersection graphs over minor-closed graph families. A key intermediate step in Lee's approach was a padded decomposition scheme for region intersection graphs. In 2024, Korhonen and Lokshtanov extended Lee's approach to the broader setting of graph classes excluding a fixed graph as an induced minor. These results have since found applications in a wide range of works. Later in 2024, a flaw was discovered in the construction of Lee's padded decomposition scheme, invalidating Lee's as well as Korhonen and Lokshtanov's separator results, and many works relying on them. In this work, we prove that string graphs with m edges admit balanced separators of size 𝒪(√m), and more generally obtain analogous 𝒪(√m) bounds for region intersection graphs over fixed minor-closed graph families and for graphs excluding a fixed graph as an induced minor, thereby repairing the vast majority of the affected works. Furthermore, our balanced separators can be found in polynomial time. Our proof uses a different approach from Lee's and does not rely on padded decompositions. Since padded decompositions have also found applications independent of the separator theorems, particularly for string graphs, we also prove a padded decomposition result for region intersection graphs that is optimal for string graphs. We have formalized both the balanced separator and the padded decomposition results in Lean 4 with mathlib.
Related
- On separators in Kt-minor-free graphs
- Kh-Minor-Free Graphs Have Balanced Separators of Size O(h√n)
- QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
- Inverse KLT kernel of AdS string integrals from the intersection matrix
- Intersection Orbital Graphs of Permutation Groups and Reconstruction of Simple Groups
BibTeX
@misc{davies2026revisiting,
title = {{Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs}},
author = {James Davies and Paweł Rzążewski and Jack Spalding-Jamieson and Bartosz Walczak},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23792},
eprint = {2610.23792},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23792},
}
RIS
TY - UNPB
TI - Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs
AU - James Davies
AU - Paweł Rzążewski
AU - Jack Spalding-Jamieson
AU - Bartosz Walczak
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23792
UR - https://arxiv.org/abs/2610.23792
AB - String graphs are intersection graphs of continuous curves in the plane. In 2010, Fox and Pach proved that string graphs with m edges admit balanced vertex separators of size 𝒪(m^3/4√(log m)) and conjectured that this bound can be improved to 𝒪(√m), which would be optimal. After partial progress, Lee claimed in 2017 to prove this conjecture, and more generally to prove analogous separator theorems for region intersection graphs over minor-closed graph families. A key intermediate step in Lee's approach was a padded decomposition scheme for region intersection graphs. In 2024, Korhonen and Lokshtanov extended Lee's approach to the broader setting of graph classes excluding a fixed graph as an induced minor. These results have since found applications in a wide range of works. Later in 2024, a flaw was discovered in the construction of Lee's padded decomposition scheme, invalidating Lee's as well as Korhonen and Lokshtanov's separator results, and many works relying on them. In this work, we prove that string graphs with m edges admit balanced separators of size 𝒪(√m), and more generally obtain analogous 𝒪(√m) bounds for region intersection graphs over fixed minor-closed graph families and for graphs excluding a fixed graph as an induced minor, thereby repairing the vast majority of the affected works. Furthermore, our balanced separators can be found in polynomial time. Our proof uses a different approach from Lee's and does not rely on padded decompositions. Since padded decompositions have also found applications independent of the separator theorems, particularly for string graphs, we also prove a padded decomposition result for region intersection graphs that is optimal for string graphs. We have formalized both the balanced separator and the padded decomposition results in Lean 4 with mathlib.
ER -