String graphs and related classes admit optimal small balanced separators
Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs
Computational GeometryDiscrete Mathematics
Summary
Graph researchers have studied how to break complex graphs made from curves or regions into smaller parts using special vertex sets called separators. Previous work claimed to find optimally small separators for such graphs, but a flaw was found that invalidated those proofs and affected many results relying on them. The authors have now fixed this by proving optimal-size separators exist and can be found efficiently for these graphs using a different method. They also improved a technical tool called padded decompositions that had independent uses. All their results have been formally verified in a computer proof system.
What this means in practice
- •For graph algorithm engineers: Develop algorithms for large geometric or topological graphs by reliably dividing them into balanced parts using guaranteed small separators from this work.
- •For computational geometry software developers: Improve efficiency in processing graphs derived from planar curve intersections by applying the new polynomial-time method to find balanced vertex separators.
Authors
James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, Bartosz Walczak
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 $\mathcal{O}(m^{3/4}\sqrt{\log m})$ and conjectured that this bound can be improved to $\mathcal{O}(\sqrt{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 $\mathcal{O}(\sqrt{m})$, and more generally obtain analogous $\mathcal{O}(\sqrt{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.