{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T08:35:34Z","timestamp":1725525334297},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642002014"},{"type":"electronic","value":"9783642002021"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-00202-1_1","type":"book-chapter","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T07:34:01Z","timestamp":1234251241000},"page":"1-14","source":"Crossref","is-referenced-by-count":2,"title":["A Separator Theorem for String Graphs and Its Applications"],"prefix":"10.1007","author":[{"given":"Jacob","family":"Fox","sequence":"first","affiliation":[]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1090\/S0894-0347-1990-1065053-0","volume":"3","author":"N. Alon","year":"1990","unstructured":"Alon, N., Seymour, P., Thomas, R.: A separator theorem for nonplanar graphs. J. Amer. Math. Soc.\u00a03, 801\u2013808 (1990)","journal-title":"J. Amer. Math. Soc."},{"key":"1_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory","author":"B. Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Springer, Heidelberg (1998)"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"B\u00f6ttcher, J., Pruessmann, K.P., Taraz, A., W\u00fcrfl, A.: Bandwidth, treewidth, separators, expansion, and universality, in. In: Proc. Topological. and Geometric Graph Theory (TGGT 2008); Electron. Notes. Discrete Math., vol.\u00a031, pp. 91\u201396 (2008)","DOI":"10.1016\/j.endm.2008.06.018"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0095-8956(92)90003-G","volume":"56","author":"V. Capoyleas","year":"1992","unstructured":"Capoyleas, V., Pach, J.: A Tur\u00e1n-type theorem on chords of a convex polygon. J. Combinatorial Theory, Ser. B\u00a056, 9\u201315 (1992)","journal-title":"J. Combinatorial Theory, Ser. B"},{"key":"1_CR5","first-page":"151","volume-title":"Selected Topics in Graph Theory","author":"F. Chung","year":"1988","unstructured":"Chung, F.: Labelings of graphs. In: Selected Topics in Graph Theory, pp. 151\u2013168. Academic Press, San Diego (1988)"},{"key":"1_CR6","volume-title":"Graph Theory","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory, 2nd edn. Springer, Heidelberg (2000)","edition":"2"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P. Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P.: Graph theory and probability. Canad. J. Math.\u00a011, 34\u201338 (1959)","journal-title":"Canad. J. Math."},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/s11083-006-9043-z","volume":"23","author":"J. Fox","year":"2006","unstructured":"Fox, J.: A bipartite analogue of Dilworth\u2019s theorem. Order\u00a023, 197\u2013209 (2006)","journal-title":"Order"},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1016\/j.aim.2008.06.002","volume":"219","author":"J. Fox","year":"2008","unstructured":"Fox, J., Pach, J.: Separator theorems and Tur\u00e1n-type results for planar intersection graphs. Advances in Mathematics\u00a0219, 1070\u20131080 (2008)","journal-title":"Advances in Mathematics"},{"key":"1_CR10","first-page":"346","volume-title":"Proc. 24th ACM Sympos. on Computational Geometry","author":"J. Fox","year":"2008","unstructured":"Fox, J., Pach, J.: Coloring K k -free intersection graphs of geometric objects in the plane. In: Proc. 24th ACM Sympos. on Computational Geometry, pp. 346\u2013354. ACM Press, New York (2008)"},{"key":"1_CR11","unstructured":"Fox, J., Pach, J.: String graphs and incomparability graphs (manuscript)"},{"key":"1_CR12","unstructured":"Fox, J., Pach, J., T\u00f3th, C.D.: Intersection patterns of curves. J. London Math. Soc. (to appear)"},{"key":"1_CR13","unstructured":"Fox, J., Pach, J., T\u00f3th, C.D.: Tur\u00e1n-type results for partial orders and intersection graphs of convex sets. Israel J. Math. (to appear)"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/0196-6774(84)90019-1","volume":"5","author":"J.R. Gilbert","year":"1984","unstructured":"Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. J. Algorithms\u00a05, 391\u2013407 (1984)","journal-title":"J. Algorithms"},{"key":"1_CR15","first-page":"141","volume":"88","author":"P. Koebe","year":"1936","unstructured":"Koebe, P.: Kontaktprobleme der konformen Abbildung. Berichte \u00fcber die Verhandlungen der Sachsischen Akademie der Wissenschaften, Leipzig. Mathematische-Physische Klasse\u00a088, 141\u2013164 (1936)","journal-title":"Mathematische-Physische Klasse"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.jctb.2003.09.002","volume":"92","author":"P. Kolman","year":"2004","unstructured":"Kolman, P., Matou\u0161ek, J.: Crossing number, pair-crossing number, and expansion. J. Combin. Theory Ser. B\u00a092, 99\u2013113 (2004)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1006\/eujc.1997.0151","volume":"19","author":"A.V. Kostochka","year":"1998","unstructured":"Kostochka, A.V., Ne\u0161et\u0159il, J.: Coloring relatives of intervals on the plane. I. Chromatic number versus girth. European J. Combin.\u00a019, 103\u2013110 (1998)","journal-title":"European J. Combin."},{"key":"1_CR18","first-page":"761","volume":"30","author":"J. Kratochv\u00edl","year":"1989","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: NP-hardness results for intersection graphs. Comment. Math. Univ. Carolin.\u00a030, 761\u2013773 (1989)","journal-title":"Comment. Math. Univ. Carolin."},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1006\/jctb.1994.1071","volume":"62","author":"J. Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: Intersection graphs of segments. J. Combin. Theory Ser. B\u00a062, 289\u2013315 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00493-004-0017-8","volume":"24","author":"D. K\u00fchn","year":"2004","unstructured":"K\u00fchn, D., Osthus, D.: Induced subdivisions in K s,s -free graphs of large average degree. Combinatorica\u00a024, 287\u2013304 (2004)","journal-title":"Combinatorica"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal.\u00a016, 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math.\u00a036, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput.\u00a09, 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"G.L. Miller","year":"1997","unstructured":"Miller, G.L., Teng, S.-H., Thurston, W., Vavasis, S.A.: Separators for sphere-packings and nearest neighbor graphs. J. ACM\u00a044, 1\u201329 (1997)","journal-title":"J. ACM"},{"key":"1_CR25","doi-asserted-by":"publisher","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial Geometry","author":"J. Pach","year":"1995","unstructured":"Pach, J., Agarwal, P.: Combinatorial Geometry. J. Wiley, New York (1995)"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s00373-005-0616-1","volume":"21","author":"J. Pach","year":"2005","unstructured":"Pach, J., Pinchasi, R., Sharir, M., T\u00f3th, G.: Topological graphs with no large grids. Graphs and Combinatorics\u00a021, 355\u2013364 (2005)","journal-title":"Graphs and Combinatorics"},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/jgt.20332","volume":"59","author":"J. Pach","year":"2008","unstructured":"Pach, J., Sharir, M.: On planar intersection graphs with forbidden subgraphs. J. Graph Theory\u00a059, 205\u2013214 (2008)","journal-title":"J. Graph Theory"},{"key":"1_CR28","first-page":"150","volume":"15","author":"J. Pach","year":"2006","unstructured":"Pach, J., T\u00f3th, G.: Comment on Fox News. Geombinatorics\u00a015, 150\u2013154 (2006)","journal-title":"Geombinatorics"},{"key":"1_CR29","series-title":"Texts and Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational geometry. An introduction","author":"F. Preparata","year":"1985","unstructured":"Preparata, F., Shamos, M.: Computational geometry. An introduction. Texts and Monographs in Computer Science. Springer, New York (1985)"},{"key":"1_CR30","doi-asserted-by":"crossref","unstructured":"Radoi\u010di\u0107, R., T\u00f3th, G.: The discharging method in combinatorial geometry and its application to Pach\u2013Sharir conjecture on intersection graphs. In: Goodman, J.E., Pach, J., Pollack, J. (eds.) Proceedings of the Joint Summer Research Conference on Discrete and Computational Geometry. Contemporary Mathematics, AMS, vol.\u00a0453, pp. 319\u2013342 (2008)","DOI":"10.1090\/conm\/453\/08806"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0095-8956(83)90067-9","volume":"35","author":"C. Thomassen","year":"1983","unstructured":"Thomassen, C.: Girth in graphs. J. Combin. Theory Ser. B\u00a035, 129\u2013141 (1983)","journal-title":"J. Combin. Theory Ser. B"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-00202-1_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T23:07:36Z","timestamp":1558134456000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-00202-1_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642002014","9783642002021"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-00202-1_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}