{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T20:10:19Z","timestamp":1743106219832,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319501055"},{"type":"electronic","value":"9783319501062"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-50106-2_32","type":"book-chapter","created":{"date-parts":[[2016,12,7]],"date-time":"2016-12-07T15:22:42Z","timestamp":1481124162000},"page":"413-426","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximating the Rectilinear Crossing Number"],"prefix":"10.1007","author":[{"given":"Jacob","family":"Fox","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Suk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,8]]},"reference":[{"key":"32_CR1","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/s00454-012-9403-y","volume":"48","author":"BM \u00c1brego","year":"2012","unstructured":"\u00c1brego, B.M., Cetina, M., Fern\u00e1ndez-Merchant, S., Lea\u00f1os, J., Salazar, G.: On $$(\\le k)$$-edges, crossings, and halving lines of geometric drawings of $$K_n$$. Discret. Comput. Geom. 48, 192\u2013215 (2012)","journal-title":"Discret. Comput. Geom."},{"key":"32_CR2","first-page":"5","volume-title":"Thirty Essays on Geometric Graph Theory","author":"B \u00c1brego","year":"2012","unstructured":"\u00c1brego, B., Fern\u00e1ndez-Merchant, S., Salazar, G.: The rectilinear crossing number of $$K_n$$: closing in (or are we?). Thirty Essays on Geometric Graph Theory, pp. 5\u201318. Springer, Heidelberg (2012)"},{"key":"32_CR3","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1023\/A:1021231927255","volume":"19","author":"O Aichholzer","year":"2002","unstructured":"Aichholzer, O., Aurenhammer, F., Krasser, H.: Enumerating order types for small point sets with applications. Order 19, 265\u2013281 (2002)","journal-title":"Order"},{"key":"32_CR4","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.comgeo.2005.07.005","volume":"36","author":"O Aichholzer","year":"2007","unstructured":"Aichholzer, O., Krasser, H.: Abstract order type extension and new results on the rectilinear crossing number. Comput. Geom. 36, 2\u201315 (2007). Special Issue on the 21st European Workshop on Computational Geometry","journal-title":"Comput. Geom."},{"key":"32_CR5","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/S0304-0208(08)73484-4","volume-title":"Theory and Practice of Combinatorics - A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday","author":"M. Ajtai","year":"1982","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M., Szemer\u00e9di, E.: Crossing-free subgraphs. In: Theory and practice of combinatorics, North Holland Mathematics Studies, vol. 60, pp. 9\u201312 (1982)"},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56, 37 (2009)","journal-title":"J. ACM"},{"key":"32_CR7","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S Basu","year":"1996","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43, 1002\u20131045 (1996)","journal-title":"J. ACM"},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/BF02574701","volume":"6","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D.: Some provably hard crossing number problems. Discret. Comput. Geom. 6, 443\u2013459 (1991)","journal-title":"Discret. Comput. Geom."},{"key":"32_CR9","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1002\/jgt.3190170308","volume":"17","author":"D Bienstock","year":"1993","unstructured":"Bienstock, D., Dean, N.: Bounds for rectilinear crossing numbers. J. Graph Theory 17, 333\u2013348 (1993)","journal-title":"J. Graph Theory"},{"key":"32_CR10","volume-title":"Oriented Matroids","author":"A Bj\u00f6rner","year":"1993","unstructured":"Bj\u00f6rner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.: Oriented Matroids. Cambridge University Press, Cambridge (1993)"},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"1801","DOI":"10.1016\/j.aim.2008.07.008","volume":"219","author":"C Borgs","year":"2008","unstructured":"Borgs, C., Chayes, J.T., Lov\u00e1sz, L., S\u00f3s, V.T., Vesztergombi, K.: Convergent sequences of dense graphs I: subgraph frequencies, metric properties and testing. Adv. Math. 219, 1801\u20131851 (2008)","journal-title":"Adv. Math."},{"key":"32_CR12","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF02125347","volume":"9","author":"FRK Chung","year":"1989","unstructured":"Chung, F.R.K., Graham, R.L., Wilson, R.M.: Quasi-random graphs. Combinatorica 9, 345\u2013362 (1989)","journal-title":"Combinatorica"},{"key":"32_CR13","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1007\/s00039-012-0171-x","volume":"22","author":"D Conlon","year":"2012","unstructured":"Conlon, D., Fox, J.: Bounds for graph regularity and removal lemmas. Geom. Funct. Anal. 22, 1191\u20131256 (2012)","journal-title":"Geom. Funct. Anal."},{"key":"32_CR14","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J.: An algorithm for the graph crossing number problem. In: Proceedings of the 43rd annual ACM Symposium on Theory of Computing, pp. 303\u2013312 (2011)","DOI":"10.1145\/1993636.1993678"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1017\/S0963548314000200","volume":"24","author":"D Dellamonica","year":"2015","unstructured":"Dellamonica, D., Kalyanasundaram, S., Martin, D., R\u00f6dl, V., Shapira, A.: An optimal algorithm for finding Frieze-Kannan regular partitions. Comb. Probab. Comput. 24, 407\u2013437 (2015)","journal-title":"Comb. Probab. Comput."},{"key":"32_CR16","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1137\/S0097539700373520","volume":"32","author":"G Even","year":"2002","unstructured":"Even, G., Guha, S., Schieber, B.: Improved approximations of crossings in graph drawings and VLSI layout areas. SIAM J. Comput. 32, 231\u2013252 (2002)","journal-title":"SIAM J. Comput."},{"key":"32_CR17","doi-asserted-by":"publisher","first-page":"393","DOI":"10.7155\/jgaa.00328","volume":"18","author":"R Faila-Monroy","year":"2014","unstructured":"Faila-Monroy, R., L\u00f3pez, J.: Computational search of small point sets with small rectilinear crossing number. J. Graph Algorithms Appl. 18, 393\u2013399 (2014)","journal-title":"J. Graph Algorithms Appl."},{"key":"32_CR18","first-page":"229","volume":"11","author":"I F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I.: On straight line representation of planar graphs. Acta Univ. Szeged. Sect. Math. 11, 229\u2013233 (1948)","journal-title":"Acta Univ. Szeged. Sect. Math."},{"key":"32_CR19","unstructured":"Fox, J., Lov\u00e1sz, L.M.: A tight lower bound for Szemer\u00e9di\u2019s regularity lemma (preprint)"},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"Fox, J., Pach, J., Suk, A.: Density, regularity theorems for semi-algebraic hypergraphs. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2115). San Diego, pp. 1517\u20131530 (2015)","DOI":"10.1137\/1.9781611973730.100"},{"key":"32_CR21","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s004930050052","volume":"19","author":"A Frieze","year":"1999","unstructured":"Frieze, A., Kannan, R.: Quick approximation to matrices and applications. Combinatorica 19, 175\u2013220 (1999)","journal-title":"Combinatorica"},{"key":"32_CR22","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-642-58043-7_6","volume-title":"New Trends in Discrete and Computational Geometry","author":"JE Goodman","year":"1993","unstructured":"Goodman, J.E., Pollack, R.: Allowable sequences and order types in discrete and computational geometry. In: Pach, J. (ed.) New Trends in Discrete and Computational Geometry. Algorithms and Combinatorics, vol. 10, pp. 103\u2013134. Springer, Heidelberg (1993)"},{"key":"32_CR23","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1137\/0212032","volume":"12","author":"JE Goodman","year":"1983","unstructured":"Goodman, J.E., Pollack, R.: Multidimensional sorting. SIAM J. Comput. 12, 484\u2013507 (1983)","journal-title":"SIAM J. Comput."},{"key":"32_CR24","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/PL00001621","volume":"7","author":"WT Gowers","year":"1997","unstructured":"Gowers, W.T.: Lower bounds of tower type for Szemer\u00e9di\u2019s uniformity lemma. Geom. Funct. Anal. 7, 322\u2013337 (1997)","journal-title":"Geom. Funct. Anal."},{"key":"32_CR25","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM 21, 549\u2013568 (1974)","journal-title":"J. ACM"},{"key":"32_CR26","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.: Computing crossing number in linear time. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC 2007), pp. 382\u2013390. ACM, New York (2007)","DOI":"10.1145\/1250790.1250848"},{"key":"32_CR27","series-title":"Foundations of Computing Series","volume-title":"Complexity Issues in VLSI","author":"FT Leighton","year":"1983","unstructured":"Leighton, F.T.: Complexity Issues in VLSI. Foundations of Computing Series. MIT Press, Cambridge (1983)"},{"key":"32_CR28","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"FT Leighton","year":"1999","unstructured":"Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46, 787\u2013832 (1999)","journal-title":"J. ACM"},{"key":"32_CR29","series-title":"American Mathematical Society Colloquium Publications","doi-asserted-by":"crossref","DOI":"10.1090\/coll\/060","volume-title":"Large Networks and Graph Limits","author":"L Lov\u00e1sz","year":"2012","unstructured":"Lov\u00e1sz, L.: Large Networks and Graph Limits. American Mathematical Society Colloquium Publications, vol. 60. American Mathematical Society, Providence (2012)"},{"key":"32_CR30","unstructured":"Pach, J., Sz\u00e9kely, L., T\u00f3th, C.D., T\u00f3th, G.: Note on $$k$$-planar crossing numbers (manuscript)"},{"key":"32_CR31","first-page":"195","volume":"9","author":"J Pach","year":"2000","unstructured":"Pach, J., T\u00f3th, G.: Thirteen problems on crossing numbers. Geombinatorics 9, 195\u2013207 (2000)","journal-title":"Geombinatorics"},{"key":"32_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-11805-0_32","volume-title":"Graph Drawing","author":"M Schaefer","year":"2010","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 334\u2013344. Springer, Heidelberg (2010). doi:\n                      10.1007\/978-3-642-11805-0_32"},{"key":"32_CR33","doi-asserted-by":"crossref","unstructured":"Schaefer, M.: The graph crossing number, its variants: a survey, Electron. J. Combin. DS21, 100 (2014)","DOI":"10.37236\/2713"},{"key":"32_CR34","doi-asserted-by":"publisher","first-page":"939","DOI":"10.2307\/2975158","volume":"101","author":"E Scheinerman","year":"1994","unstructured":"Scheinerman, E., Wilf, H.S.: The rectilinear crossing number of a complete graph and Sylvester\u2019s \"four point\" problem of geometric probability. Am. Math. Mon. 101, 939\u2013943 (1994)","journal-title":"Am. Math. Mon."},{"key":"32_CR35","unstructured":"Moshkovitz, G., Shapira, A.: A short proof of Gowers\u2019 lower bound for the regularity lemma (preprint)"},{"key":"32_CR36","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1002\/rsa.10053","volume":"21","author":"J Spencer","year":"2002","unstructured":"Spencer, J., T\u00f3th, G.: Crossing numbers of random graphs. Random Struct. Algorithms 21, 347\u2013358 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"32_CR37","volume-title":"Question 1491","author":"JJ Sylvester","year":"1864","unstructured":"Sylvester, J.J.: Question 1491. The Educational Times, London (1864)"},{"key":"32_CR38","first-page":"8","volume":"35","author":"JJ Sylvester","year":"1865","unstructured":"Sylvester, J.J.: Rep. Br. Assoc. 35, 8\u20139 (1865)","journal-title":"Rep. Br. Assoc."},{"key":"32_CR39","unstructured":"Szemer\u00e9di, E.: Regular partitions of graphs. In: Probl\u00e8mes combinatoires et th\u00e9orie des graphes (Colloq. Internat. CNRS, Univ. Orsay), vol. 260, pp. 399\u2013401. CNRS, Paris (1978)"},{"key":"32_CR40","unstructured":"Vrt\u2019o, I.: Crossing numbers bibliography. \n                      www.ifi.savba.sk\/~imrich"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing and Network Visualization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-50106-2_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,19]],"date-time":"2020-09-19T00:42:55Z","timestamp":1600476175000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-50106-2_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319501055","9783319501062"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-50106-2_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"8 December 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"GD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Graph Drawing and Network Visualization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}