{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T04:50:56Z","timestamp":1774500656300,"version":"3.50.1"},"reference-count":39,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2009,10,7]],"date-time":"2009-10-07T00:00:00Z","timestamp":1254873600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2010,5]]},"abstract":"<jats:p>A <jats:italic>string graph<\/jats:italic> is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with <jats:italic>m<\/jats:italic> edges can be separated into two parts of roughly equal size by the removal of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548309990459_inline1\"><jats:alt-text>$O(m^{3\/4}\\sqrt{\\log m})$<\/jats:alt-text><\/jats:inline-graphic> vertices. This result is then used to deduce that every string graph with <jats:italic>n<\/jats:italic> vertices and no complete bipartite subgraph <jats:italic>K<jats:sub>t,t<\/jats:sub><\/jats:italic> has at most <jats:italic>c<jats:sub>t<\/jats:sub>n<\/jats:italic> edges, where <jats:italic>c<jats:sub>t<\/jats:sub><\/jats:italic> is a constant depending only on <jats:italic>t<\/jats:italic>. Another application shows that locally tree-like string graphs are globally tree-like: for any \u03b5 &gt; 0, there is an integer <jats:italic>g<\/jats:italic>(\u03b5) such that every string graph with <jats:italic>n<\/jats:italic> vertices and girth at least <jats:italic>g<\/jats:italic>(\u03b5) has at most (1 + \u03b5)<jats:italic>n<\/jats:italic> edges. Furthermore, the number of such labelled graphs is at most (1 + \u03b5)<jats:italic><jats:sup>n<\/jats:sup><\/jats:italic><jats:italic>T<\/jats:italic>(<jats:italic>n<\/jats:italic>), where <jats:italic>T<\/jats:italic>(<jats:italic>n<\/jats:italic>) = <jats:italic>n<\/jats:italic><jats:sup><jats:italic>n<\/jats:italic>\u22122<\/jats:sup> is the number of labelled trees on <jats:italic>n<\/jats:italic> vertices.<\/jats:p>","DOI":"10.1017\/s0963548309990459","type":"journal-article","created":{"date-parts":[[2009,10,7]],"date-time":"2009-10-07T04:32:33Z","timestamp":1254889953000},"page":"371-390","source":"Crossref","is-referenced-by-count":37,"title":["A Separator Theorem for String Graphs and its Applications"],"prefix":"10.1017","volume":"19","author":[{"given":"JACOB","family":"FOX","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00c1NOS","family":"PACH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,10,7]]},"reference":[{"key":"S0963548309990459_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90067-9"},{"key":"S0963548309990459_ref38","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1090\/conm\/453\/08806","volume-title":"Proc. Joint Summer Research Conference on Discrete and Computational Geometry","author":"Radoi\u010di\u0107","year":"2008"},{"key":"S0963548309990459_ref34","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20332"},{"key":"S0963548309990459_ref31","doi-asserted-by":"publisher","DOI":"10.1002\/9781118033203"},{"key":"S0963548309990459_ref13","unstructured":"[13] Fox J. and Pach J. String graphs and incomparability graphs. Submitted."},{"key":"S0963548309990459_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/BF02086610"},{"key":"S0963548309990459_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-005-0616-1"},{"key":"S0963548309990459_ref27","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"S0963548309990459_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.09.007"},{"key":"S0963548309990459_ref12","first-page":"346","volume-title":"Proc. 24th ACM Sympos. on Computational Geometry","author":"Fox","year":"2008"},{"key":"S0963548309990459_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0017-8"},{"key":"S0963548309990459_ref20","volume-title":"Infinite Sequences and Series","author":"Knopp","year":"1956"},{"key":"S0963548309990459_ref26","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"S0963548309990459_ref17","first-page":"141","article-title":"Kontaktprobleme der konformen Abbildung. Berichte \u00fcber die Verhandlungen der Sachsischen Akademie der Wissenschaften, Leipzig","volume":"88","author":"Koebe","year":"1936","journal-title":"Mathematische-Physische Klasse"},{"key":"S0963548309990459_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-006-9043-z"},{"key":"S0963548309990459_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.06.002"},{"key":"S0963548309990459_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"S0963548309990459_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"S0963548309990459_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2008.06.018"},{"key":"S0963548309990459_ref1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"S0963548309990459_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.09.002"},{"key":"S0963548309990459_ref19","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0151"},{"key":"S0963548309990459_ref29","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256294"},{"key":"S0963548309990459_ref35","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1978"},{"key":"S0963548309990459_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"S0963548309990459_ref8","unstructured":"[8] Dvo\u0159\u00e1k Z. and Norine S. Small graph classes and bounded expansion. J. Combin. Theory Ser. B, to appear."},{"key":"S0963548309990459_ref6","first-page":"151","volume-title":"Selected Topics in Graph Theory","author":"Chung","year":"1988"},{"key":"S0963548309990459_ref22","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1071"},{"key":"S0963548309990459_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"S0963548309990459_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90003-G"},{"key":"S0963548309990459_ref15","unstructured":"[15] Fox J. , Pach J. and T\u00f3th C. D. Tur\u00e1n-type results for partial orders and intersection graphs of convex sets. Israel J. Math, to appear."},{"key":"S0963548309990459_ref25","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"S0963548309990459_ref21","first-page":"761","article-title":"NP-hardness results for intersection graphs","volume":"30","author":"Kratochv\u00edl","year":"1989","journal-title":"Comment. Math. Univ. Carolin."},{"key":"S0963548309990459_ref7","volume-title":"Graph Theory","author":"Diestel","year":"2000"},{"key":"S0963548309990459_ref9","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1959-003-9"},{"key":"S0963548309990459_ref14","unstructured":"[14] Fox J. , Pach J. and T\u00f3th C. D. Intersection patterns of curves. J. London Math. Soc., to appear."},{"key":"S0963548309990459_ref36","first-page":"150","article-title":"Comment on Fox News","volume":"15","author":"Pach","year":"2006","journal-title":"Geombinatorics"},{"key":"S0963548309990459_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.01.006"},{"key":"S0963548309990459_ref24","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309990459","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T16:02:32Z","timestamp":1556467352000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309990459\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,7]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["S0963548309990459"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309990459","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,7]]}}}