{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:31:23Z","timestamp":1725568283552},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671817"},{"type":"electronic","value":"9783540465157"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/978-3-540-46515-7_23","type":"book-chapter","created":{"date-parts":[[2010,10,20]],"date-time":"2010-10-20T09:35:28Z","timestamp":1287567328000},"page":"267-273","source":"Crossref","is-referenced-by-count":5,"title":["Crossing Numbers"],"prefix":"10.1007","author":[{"given":"J\u00e1nos","family":"Pach","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01196127","volume":"17","author":"P. Agarwal","year":"1997","unstructured":"Agarwal, P., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear number of edges. Combinatorica\u00a017, 1\u20139 (1997)","journal-title":"Combinatorica"},{"key":"23_CR2","first-page":"9","volume":"12","author":"M. Ajtai","year":"1982","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M., Szemer\u00e9di, E.: Crossing-free subgraphs. Annals of Discrete Mathematics\u00a012, 9\u201312 (1982)","journal-title":"Annals of Discrete Mathematics"},{"key":"23_CR3","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. Journal of Graph Theory\u00a017, 333\u2013348 (1993)","journal-title":"Journal of Graph Theory"},{"key":"23_CR4","doi-asserted-by":"crossref","first-page":"135","DOI":"10.4064\/fm-23-1-135-142","volume":"23","author":"C.. Chojnacki","year":"1934","unstructured":"Chojnacki, C., Hanani, A.: \u00dcber wesentlich unpl\u00e4ttbare Kurven im dreidimensionalen Raume. Fund. Math.\u00a023, 135\u2013142 (1934)","journal-title":"Fund. Math."},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02187783","volume":"5","author":"K. Clarkson","year":"1990","unstructured":"Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., Welzl, E.: Combinatorial complexity bounds for arrangements of curves and surfaces. Discrete and Computational Geometry\u00a05, 99\u2013160 (1990)","journal-title":"Discrete and Computational Geometry"},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/PL00009354","volume":"19","author":"T.K. Dey","year":"1998","unstructured":"Dey, T.K.: Improved bounds for planar k-sets and related problems. Discrete and Computat. Geometry\u00a019, 373\u2013382 (1998)","journal-title":"Discrete and Computat. Geometry"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"52","DOI":"10.2307\/2319261","volume":"80","author":"P. Erd\u00f6s","year":"1973","unstructured":"Erd\u00f6s, P., Guy, R.K.: Crossing number problems. American Mathematical Monthly\u00a080, 52\u201358 (1973)","journal-title":"American Mathematical Monthly"},{"key":"23_CR8","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. Sci. Math.\u00a011, 229\u2013233 (1948)","journal-title":"Acta Univ. Szeged. Sect. Sci. Math."},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M.R. Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM Journal of Algebraic and Disccrete Methods\u00a04, 312\u2013316 (1983)","journal-title":"SIAM Journal of Algebraic and Disccrete Methods"},{"key":"23_CR10","first-page":"63","volume-title":"Proof Techniques in Graph Theory","author":"R.K. Guy","year":"1969","unstructured":"Guy, R.K.: The decline and fall of Zarankiewicz\u2019s theorem. In: Proof Techniques in Graph Theory, pp. 63\u201369. Academic Press, New York (1969)"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0021-9800(70)80087-4","volume":"9","author":"D.J. Kleitman","year":"1970","unstructured":"Kleitman, D.J.: The crossing number of K5, n . Journal of Combinatorial Theory\u00a09, 315\u2013323 (1970)","journal-title":"Journal of Combinatorial Theory"},{"key":"23_CR12","series-title":"Foundations of Computing Series","volume-title":"Complexity Issues in VLSI","author":"T. Leighton","year":"1983","unstructured":"Leighton, T.: Complexity Issues in VLSI. Foundations of Computing Series. MIT Press, Cambridge (1983)"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01744433","volume":"17","author":"F.T. Leighton","year":"1984","unstructured":"Leighton, F.T.: New lower bound techniques for VLSI. Math. Systems Theory\u00a017, 47\u201370 (1984)","journal-title":"Math. Systems Theory"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. Lipton","year":"1979","unstructured":"Lipton, R., Tarjan, R.: A separator theorem for planar graphs. SIAM J. Applied Mathematics\u00a036, 177\u2013189 (1979)","journal-title":"SIAM J. Applied Mathematics"},{"key":"23_CR15","doi-asserted-by":"crossref","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial Geometry","author":"J. Pach","year":"1995","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial Geometry. J. Wiley and Sons, New York (1995)"},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02086610","volume":"16","author":"J. Pach","year":"1996","unstructured":"Pach, J., Shahrokhi, F., Szegedy, M.: Applications of the crossing number. Algorithmica\u00a016, 111\u2013117 (1996)","journal-title":"Algorithmica"},{"key":"23_CR17","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1017\/S0963548397003192","volume":"7","author":"J. Pach","year":"1998","unstructured":"Pach, J., Sharir, M.: On the number of incidences between points and curves. Combinatorics, Probability and Computing\u00a07, 121\u2013127 (1998)","journal-title":"Combinatorics, Probability and Computing"},{"key":"#cr-split#-23_CR18.1","doi-asserted-by":"crossref","unstructured":"Pach, J., Spencer, J., T??th, G.: New bounds on crossing numbers. In: 15th ACM Symposium on Computational Geometry, pp. 124???133 (1999);","DOI":"10.1145\/304893.304943"},{"key":"#cr-split#-23_CR18.2","doi-asserted-by":"crossref","unstructured":"Pach, J., Spencer, J., T\u00f3th, G.: New bounds on crossing numbers. In: 15th ACM Symposium on Computational Geometry, pp. 124\u2013133 (1999); Also in: Discrete and Computational Geometry (accepted)","DOI":"10.1145\/304893.304943"},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF01215922","volume":"17","author":"J. Pach","year":"1997","unstructured":"Pach, J., T\u00f3th, G.: Graphs drawn with few crossings per edge. Combinatorica\u00a017, 427\u2013439 (1997)","journal-title":"Combinatorica"},{"key":"23_CR20","unstructured":"Pach, J., T\u00f3th, G.: Which crossing number is it, anyway? In: Proceedings of 39th Annual Symposium on Foundations of Computer Science, Palo Alto, pp. 617\u2013626 (1998)"},{"key":"23_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/3-540-37623-2_20","volume-title":"Graph Drawing","author":"J. Pach","year":"1999","unstructured":"Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol.\u00a01547, p. 263. Springer, Heidelberg (1999) (to appear)"},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"Richter, R.B., Thomassen, C.: Relations between crossing numbers of complete and complete bipartite graphs. American Mathematical Monthly, 131\u2013137 (February 1997)","DOI":"10.1080\/00029890.1997.11990611"},{"key":"23_CR23","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1017\/S0963548397002976","volume":"6","author":"L.A. Sz\u00e9kel","year":"1998","unstructured":"Sz\u00e9kel, L.A.: Crossing numbers and hard Erd\u00f6s problems in discrete geometry. Combinatorics, Probability and Computing\u00a06, 353\u2013358 (1998)","journal-title":"Combinatorics, Probability and Computing"},{"key":"23_CR24","first-page":"293","volume-title":"Graph Theory and Combinatorics","author":"J. Spencer","year":"1984","unstructured":"Spencer, J., Szemer\u00e9di, E., Trotter, W.T.: Unit distances in the Euclidean plane. In: Bollob\u00e1s, B. (ed.) Graph Theory and Combinatorics, pp. 293\u2013303. Academic Press, New York (1984)"},{"key":"23_CR25","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/BF02579194","volume":"3","author":"E. Szemer\u00e9di","year":"1983","unstructured":"Szemer\u00e9di, E., Trotter, W.T.: Extremal problems in discrete geometry. Combinatorica\u00a03, 381\u2013392 (1983)","journal-title":"Combinatorica"},{"key":"23_CR26","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1002\/jgt.3190010105","volume":"1","author":"P. Tur\u00e1n","year":"1977","unstructured":"Tur\u00e1n, P.: A note of welcome. Journal of Graph Theory\u00a01, 7\u20139 (1977)","journal-title":"Journal of Graph Theory"},{"key":"23_CR27","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0021-9800(70)80007-2","volume":"8","author":"W.T. Tutte","year":"1970","unstructured":"Tutte, W.T.: Toward a theory of crossing numbers. Journal of Combinatorial Theory\u00a08, 45\u201353 (1970)","journal-title":"Journal of Combinatorial Theory"},{"key":"23_CR28","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/PL00009364","volume":"19","author":"P. Valtr","year":"1998","unstructured":"Valtr, P.: On geometric graphs with no k pairwise parallel edges. Discrete and Computational Geometry\u00a019, 461\u2013469 (1998)","journal-title":"Discrete and Computational Geometry"},{"key":"23_CR29","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1002\/jgt.3190170602","volume":"17","author":"D.R. Woodall","year":"1993","unstructured":"Woodall, D.R.: Cyclic-order graphs and Zarankiewicz\u2019s crossing-number conjecture. Journal of Graph Theory\u00a017, 657\u2013671 (1993)","journal-title":"Journal of Graph Theory"}],"container-title":["Lecture Notes in Computer Science","Discrete and Computational Geometry"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-46515-7_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T12:47:56Z","timestamp":1559738876000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-46515-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671817","9783540465157"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-46515-7_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2000]]}}}