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

• Autores: Jacob Fox, János Pach
• Localización: Advances in mathematics, ISSN 0001-8708, Vol. 219, Nº 3, 2008, págs. 1070-1080
• Idioma: inglés
• DOI: 10.1016/j.aim.2008.06.002
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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=SC1C2 such that , , and no element of C1 has a point in common with any element of C2. 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.