{"id":"arxiv/2610.23792","url":"https://arxiv.org/abs/2610.23792","tags":["math.CO","cs.CG","cs.DM","math.MG"],"score":0,"title":"Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs","domain":"math.CO","source":"arxiv","authors":["James Davies","Paweł Rzążewski","Jack Spalding-Jamieson","Bartosz Walczak"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-16","reactions":{}}