{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T18:23:37Z","timestamp":1725819817152},"publisher-location":"Pisa","reference-count":30,"publisher":"Scuola Normale Superiore","isbn-type":[{"type":"print","value":"9788876425240"},{"type":"electronic","value":"9788876425257"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-88-7642-525-7_5","type":"book-chapter","created":{"date-parts":[[2015,4,9]],"date-time":"2015-04-09T05:03:54Z","timestamp":1428555834000},"page":"61-97","source":"Crossref","is-referenced-by-count":2,"title":["String graphs and separators"],"prefix":"10.1007","author":[{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","first-page":"9","volume":"12","author":"M Ajtai","year":"1982","unstructured":"M. Ajtai, V. Chv\u00e1tal, M. M. Newborn and E. Szemer\u00e9di, Crossing-free subgraphs, Ann. Discrete Math. 12(1982), 9\u201312.","journal-title":"Ann. Discrete Math."},{"issue":"2","key":"5_CR2","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"S. Arora, S. Rao and U. Vazirani, Expander flows, geometric embeddings and graph partitioning, J. ACM 56(2) (2009), Art. 5, 37.","journal-title":"J. ACM"},{"issue":"7","key":"5_CR3","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1137\/S0895480191198768","volume":"2","author":"N Alon","year":"1994","unstructured":"N. Alon, P. Seymour and R. Thomas, Planar separators, SIAM J. Discrete Math. 2(7) (1994), 184\u2013193.","journal-title":"SIAM J. Discrete Math."},{"key":"5_CR4","volume-title":"Queneau, Raymond, Italo Calvino, et al., Oulipo Laboratory","author":"C Berge","year":"1995","unstructured":"C. Berge, Who killed the Duke of Densmore? In: \u201cQueneau, Raymond, Italo Calvino, et al., Oulipo Laboratory\u201d, Atlas Press, London, 1995."},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J Bourgain","year":"1985","unstructured":"J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985), 46\u201352.","journal-title":"Israel J. Math."},{"issue":"2","key":"5_CR6","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/s00454-012-9440-6","volume":"49","author":"S Cabello","year":"2013","unstructured":"S. Cabello, Hardness of approximation for crossing number, Discrete Comput. Geom. 49(2) (2013), 348\u2013358.","journal-title":"Discrete Comput. Geom."},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"J. Chalopin and D. Gon\u00e7alves, Every planar graph is the intersection graph of segments in the plane, In: \u201cProc. 41st Annual ACM Symposium on Theory of Computing (STOC)\u201d, New York, NY, USA, 2009, ACM, 631\u2013638.","DOI":"10.1145\/1536414.1536500"},{"issue":"3","key":"5_CR8","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/s00454-009-9196-9","volume":"43","author":"J Chalopin","year":"2010","unstructured":"J. Chalopin, D. Gon\u00e7alves and P. Ochem, Planar graphs have 1-string representations, Discrete Comput. Geom. 43(3) (2010), 626\u2013647.","journal-title":"Discrete Comput. Geom."},{"key":"5_CR9","unstructured":"J. Chuzhoy, An algorithm for the graph crossing number problem, In: \u201cProceedings of the 43rd annual ACM symposium on Theory of Computing (STOC)\u201d, (2011), 303\u2013312. Full version in arXiv:1012.0255."},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy, Y. Makarychev and A. Sidiropoulos, On graph crossing number and edge planarization, In: \u201cProceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms\u201d, SIAM, Philadelphia, PA (2011), 1050\u20131069.","DOI":"10.1137\/1.9781611973082.80"},{"issue":"1","key":"5_CR11","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1137\/S0097539700373520","volume":"32","author":"G Even","year":"2002","unstructured":"G. Even, S. Guha and B. Schieber, Improved approximations of crossings in graph drawings and VLSI layout areas, SIAM J. Comput. 32(1) (2002\/2003), 231\u2013252 (electronic).","journal-title":"SIAM J. Comput."},{"issue":"2","key":"5_CR12","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/05064299X","volume":"38","author":"U Feige","year":"2008","unstructured":"U. Feige, M. T. Hajiaghayi and J. R. Lee, Improved approximation algorithms for minimum weight vertex separators, SIAM Journal on Computing 38(2) (2008), 629\u2013657.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"5_CR13","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1017\/S0963548309990459","volume":"19","author":"J Fox","year":"2010","unstructured":"J. Fox and J. Pach, A separator theorem for string graphs and its applications, Combinatorics, Probability & Computing 19(3) (2010), 371\u2013390.","journal-title":"Combinatorics, Probability & Computing"},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1017\/S0963548313000412","volume":"23","author":"J Fox","year":"2014","unstructured":"J. Fox and J. Pach, Applications of a new separator theorem for string graphs, Combinatorics, Probability and Computing 23 (2014), 66\u201374. Preprint arXiv:1302.7228.","journal-title":"Combinatorics, Probability and Computing"},{"issue":"2","key":"5_CR15","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/j.jcss.2003.07.008","volume":"68","author":"M Grohe","year":"2004","unstructured":"M. Grohe\n                Computing crossing numbers in quadratic time, J. Comput. System Sci. 68(2) (2004), 285\u2013302.","journal-title":"J. Comput. System Sci."},{"issue":"4","key":"5_CR16","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"S. Hoory, N. Linial and A. Widgerson, Expander graphs and their applications, Bull. Am. Math. Soc., New Ser. 43 (4) (2006), 439\u2013561.","journal-title":"Bull. Am. Math. Soc., New Ser."},{"issue":"1","key":"5_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0095-8956(91)90050-T","volume":"53","author":"J Kratochv\u00edl","year":"1991","unstructured":"J. Kratochv\u00edl and J. Matou\u0161ek, String graphs requiring exponential representations, J. Combin. Theory Ser. B 53(1) (1991), 1\u20134.","journal-title":"J. Combin. Theory Ser. B"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"K. Kawarabayashi and B. Reed, Computing crossing number in linear time, In: \u201cProc. 39th Annual ACM Symposium on Theory of Computing (STOC)\u201d, 2007, 382\u2013390.","DOI":"10.1145\/1250790.1250848"},{"issue":"1","key":"5_CR19","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0095-8956(91)90091-W","volume":"52","author":"J Kratochv\u00edl","year":"1991","unstructured":"J. Kratochv\u00edl, String graphs. II: Recognizing string graphs is NP-hard, J. Comb. Theory, Ser. B 52(1) (1991), 67\u201378.","journal-title":"J. Comb. Theory, Ser. B"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01744433","volume":"17","author":"F T Leighton","year":"1984","unstructured":"F. T. Leighton, New lower bound techniques for VLSI, Math. Systems Theory, 17 (1984), 47\u201370.","journal-title":"Math. Systems Theory,"},{"key":"5_CR21","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N Linial","year":"1995","unstructured":"N. Linial, E. London and Yu. Rabinovich, The geometry of graphs and some its algorithmic applications, Combinatorica 15 (1995), 215\u2013245.","journal-title":"Combinatorica"},{"key":"5_CR22","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"F T Leighton","year":"1999","unstructured":"F. T. Leighton and S. Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. Assoc. Comput. Machin. 46 (1999), 787\u2013832.","journal-title":"J. Assoc. Comput. Machin."},{"key":"5_CR23","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1017\/S0963548313000400","volume":"23","author":"J Matou\u0161ek","year":"2014","unstructured":"J. Matou\u0161ek, Near-optimal separators in string graphs, Combinatorics, Probability and Computing 23 (2014), 135\u2013139.","journal-title":"Combinatorics, Probability and Computing"},{"key":"5_CR24","doi-asserted-by":"publisher","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial Geometry","author":"J Pach","year":"1995","unstructured":"J. Pach and P. K. Agarwal, \u201cCombinatorial Geometry\u201d John Wiley & Sons, New York, NY, 1995."},{"issue":"1\u20133","key":"5_CR25","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1007\/s00454-008-9058-x","volume":"39","author":"M J Pelsmajer","year":"2008","unstructured":"M. J. Pelsmajer, M. Schaefer and D. \u0160tefankovi\u010d, Odd crossing number and crossing number are not the same Discrete Comput. Geom. 39(1\u20133) (2008), 442\u2013454.","journal-title":"Discrete Comput. Geom."},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1006\/jctb.2000.1978","volume":"80","author":"J Pach","year":"2000","unstructured":"J. Pach and G. T\u00f3th, Which crossing number is it anyway?, J. Combin. Theory Ser. B 80 (2000), 225\u2013246.","journal-title":"J. Combin. Theory Ser. B"},{"key":"5_CR27","volume-title":"\u201cGeometry - Intuitive, Discrete, and Convex (B\u00f3lyai Society Mathematical Studies)\u201d, Vol. 24","author":"M Schaefer","year":"2014","unstructured":"M. Schaefer, Hanani\u2014Tutte and related results, In: \u201cGeometry - Intuitive, Discrete, and Convex (B\u00f3lyai Society Mathematical Studies)\u201d, Vol. 24, I. B\u00e1r\u00e1ny et al. (eds.), Springer, Berlin, 2014."},{"key":"5_CR28","unstructured":"M. Schaefer and D. \u0160tefankovi\u010d, Decidability of string graphs, J. Comput. Syst. Sci. 68 (2004), 319\u2013334. Preliminary version in Proc. 33rd Annual ACM Symposium on Theory of Computing, 2001."},{"issue":"2","key":"5_CR29","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0022-0000(03)00045-X","volume":"67","author":"M Schaefer","year":"2003","unstructured":"M. Schaefer, E. Sedgwick and D. \u0160tefankovi\u010d, Recognizing string graphs in NP, J. Comput. Syst. Sci. 67(2) (2003), 365\u2013380.","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR30","first-page":"563","volume-title":"Thirty Essays on Geometric Graph Theory","author":"G T\u00f3th","year":"2012","unstructured":"G. T\u00f3th, A better bound for pair-crossing number, In: J. Pach (ed.), \u201cThirty Essays on Geometric Graph Theory\u201d, Springer, Berlin, 2012, 563\u2013567."}],"container-title":["Geometry, Structure and Randomness in Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-88-7642-525-7_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T19:47:53Z","timestamp":1559159273000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-88-7642-525-7_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9788876425240","9788876425257"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-88-7642-525-7_5","relation":{},"subject":[],"published":{"date-parts":[[2014]]}}}