Separator theorems and Turán-type results for planar intersection graphs

We establish several geometric extensions of the Lipton-Tarjan separator theorem for planar graphs. For instance, we show that any collection C of Jordan curves in the plane with a total of m crossings has a partition into three parts C=S∪C₁∪C₂ such that , , and no element of C₁ has a point in common with any element of C₂. These results are used to obtain various properties of intersection patterns of geometric objects in the plane. In particular, we prove that if a graph G can be obtained as the intersection graph of n convex sets in the plane and it contains no complete bipartite graph Kt,t as a subgraph, then the number of edges of G cannot exceed ctn, for a suitable constant ct.