2009/10/07 by Jacob Fox, János Pach · 62 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Combinatorics #Mathematics #Bipartite graph #Discrete mathematics #String (physics) #Graph
paper · open access · doi:10.1017/s0963548309990459
published in Combinatorics Probability Computing 19(3), 371-390 (Cambridge University Press)
openalex publication_date 2009/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22
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(m3/4√(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.