Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.23792
curl -X POST /api/v1/records/arxiv/2610.23792/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.23792/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'