A Separator Theorem for String Graphs and its Applications

Abstract

A string graph is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with m edges can be separated into two parts of roughly equal size by the removal of $O(m^{3/4}\sqrt{\log m})$ vertices. This result is then used to deduce that every string graph with n vertices and no complete bipartite subgraph K t,t has at most c t n edges, where c t is a constant depending only on t . Another application shows that locally tree-like string graphs are globally tree-like: for any ε > 0, there is an integer g (ε) such that every string graph with n vertices and girth at least g (ε) has at most (1 + ε) n edges. Furthermore, the number of such labelled graphs is at most (1 + ε) n T ( n ), where T ( n ) = n n −2 is the number of labelled trees on n vertices.