Home » Subject » Graph Theory

Separators in string graphs (Solved)

Importance: Medium ✭✭
Author(s): Fox, Jacob
Pach, János
Tóth, Csaba D.
Subject: Graph Theory
Keywords: separator
string graphs
Recomm. for undergrads: no
Posted by: cibulka
on: January 1st, 2010
Solved by: James R. Lee. "Separators in region intersection graphs", arXiv:1608.01612.
Conjecture   Every string graph with $ m $ edges has a separator of size $ O(\sqrt{m}) $.

Consider a graph $ G=(V,E) $ with vertex weights $ w:V \rightarrow \mathbb R_{\geq 0} $. A separator in $ G $ is a set $ S $ of vertices such that there is a partition $ V=C_1 \cup S \cup C_2 $ of the vertices with no edge going between $ C_1 $ and $ C_2 $ and with $ w(C_1),w(C_2)\leq 2/3 $. The size of the separator $ S $ is the number of vertices of $ S $.

The result holds for planar graphs (which form a subclass of string graphs) by the Lipton-Tarjan theorem~[LT]. The best known upper bound for string graphs is currently $ O(m^{3/4} \sqrt{\log(m)}) $ from~[FP].

Update: Solved by James Lee [Lee].

Bibliography

*[FPT] Jacob Fox, János Pach, Csaba D. Tóth: Intersection patterns of curves, J. London Math. Soc., to appear

[FP] Jacob Fox, János Pach A separator theorem for string graphs and its applications, Combinatorics, Probability and Computing, to appear.

[LT] Richard J. Lipton, Robert Endre Tarjan: A separator theorem for planar graphs, SIAM Journal on Applied Mathematics 36 (1979), 177-–189.

[Lee] James R. Lee. Separators in region intersection graphs, 2016.


* indicates original appearance(s) of problem.
add new comment

Jiri Matousek has almost

On January 21st, 2014 David Wood says:

Jiri Matousek has almost solved this problem. He proves a $ O(\sqrt m \log m) $ upper bound in "Near-optimal separators in string graphs" at arXiv:1302.6482.

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.