A Sharp Threshold Phenomenon in String Graphs

A string graph is the intersection graph of curves in the plane. We prove that for every [Formula: see text] , if G is a string graph with n vertices such that the edge density of G is below [Formula: see text] , then V(G) contains two linear sized subsets A and B with no edges between them. The constant 1/4 is a sharp threshold for this phenomenon as there are string graphs with edge density less than [Formula: see text] such that there is an edge connecting any two logarithmic sized subsets of the vertices. The existence of linear sized sets A and B with no edges between them in sufficiently sparse string graphs is a direct consequence of a recent result of Lee about separators. Our main theorem finds the largest possible density for which this still holds. In the special case when the curves are x-monotone, the same result was proved by Pach and the author of this paper, who also proposed the conjecture for the general case.