{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T14:29:11Z","timestamp":1774276151764,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642034558","type":"print"},{"value":"9783642034565","type":"electronic"}],"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-03456-5_21","type":"book-chapter","created":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T02:39:16Z","timestamp":1251772756000},"page":"305-317","source":"Crossref","is-referenced-by-count":2,"title":["The Crossing Number of Graphs: Theory and Computation"],"prefix":"10.1007","author":[{"given":"Petra","family":"Mutzel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Aichholzer, O., Aurenhammer, F., Krasser, H.: On the crossing number of complete graphs. In: Symposium on Computational Geometry, pp. 19\u201324 (2002)","DOI":"10.1145\/513400.513403"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S.N. Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A framework for solving vlsi layout problems. Journal of Computer and System Sciences\u00a028, 300\u2013343 (1984)","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR3","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. Discrete & Computational Geometry\u00a06, 443\u2013459 (1991)","journal-title":"Discrete & Computational Geometry"},{"issue":"5","key":"21_CR4","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1002\/jgt.3190160502","volume":"16","author":"D. Bienstock","year":"1992","unstructured":"Bienstock, D., Dean, N.: New results on rectilinear crossing numbers and plane embeddings. J. Graph Theory\u00a016(5), 389\u2013398 (1992)","journal-title":"J. Graph Theory"},{"issue":"3","key":"21_CR5","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\u00a017(3), 333\u2013348 (1993)","journal-title":"J. Graph Theory"},{"issue":"2","key":"21_CR6","first-page":"373","volume":"5","author":"C. Buchheim","year":"2008","unstructured":"Buchheim, C., Chimani, M., Ebner, D., Gutwenger, C., J\u00fcnger, M., Klau, G.W., Mutzel, P., Weiskircher, R.: A branch-and-cut approach to the crossing number problem. Discrete Optimization, Special Issue in memory of George B. Dantzig\u00a05(2), 373\u2013388 (2008)","journal-title":"Discrete Optimization, Special Issue in memory of George B. Dantzig"},{"key":"21_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-642-00219-9_5","volume-title":"Graph Drawing","author":"S. Cabello","year":"2009","unstructured":"Cabello, S., Mohar, B.: Crossing and weighted crossing number of near-planar graphs. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol.\u00a05417, pp. 38\u201349. Springer, Heidelberg (2009)"},{"key":"21_CR8","unstructured":"Chimani, M.: Exact Crossing Minimization. PhD thesis, Fakult\u00e4t f\u00fcr Informatik, Technische Universit\u00e4t Dortmund (2008)"},{"key":"21_CR9","first-page":"375","volume-title":"SODA","author":"M. Chimani","year":"2009","unstructured":"Chimani, M., Gutwenger, C., Mutzel, P., Wolf, C.: Inserting a vertex into a planar graph. In: SODA, pp. 375\u2013383. SIAM, Philadelphia (2009)"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Chimani, M., Hlin\u011bn\u00fd, P., Mutzel, P.: Vertex insertion approximates the crossing number for apex graphs (submitted, 2009)","DOI":"10.1007\/978-3-642-00219-9_42"},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-3-540-87744-8_24","volume-title":"Algorithms - ESA 2008","author":"M. Chimani","year":"2008","unstructured":"Chimani, M., Mutzel, P., Bomze, I.: A new approach to exact crossing minimization. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 284\u2013296. Springer, Heidelberg (2008)"},{"issue":"2-3","key":"21_CR12","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s10107-006-0039-7","volume":"109","author":"E. Klerk de","year":"2007","unstructured":"de Klerk, E., Pasechnik, D.V., Schrijver, A.: Reduction of symmetric semidefinite programs using the regular *-representation. Math. Program.\u00a0109(2-3), 613\u2013624 (2007)","journal-title":"Math. Program."},{"issue":"3","key":"21_CR13","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 & Computational Geometry\u00a019(3), 373\u2013382 (1998)","journal-title":"Discrete & Computational Geometry"},{"issue":"4","key":"21_CR14","doi-asserted-by":"crossref","first-page":"365","DOI":"10.4064\/aa-81-4-365-367","volume":"81","author":"G. Elekes","year":"1997","unstructured":"Elekes, G.: On the number of sums and products. Acta Arithm.\u00a081(4), 365\u2013367 (1997)","journal-title":"Acta Arithm."},{"issue":"1","key":"21_CR15","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 Journal on Computing\u00a032(1), 231\u2013252 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"21_CR16","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s00453-004-1128-8","volume":"41","author":"C. Gutwenger","year":"2005","unstructured":"Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. Algorithmica\u00a041(4), 289\u2013308 (2005)","journal-title":"Algorithmica"},{"key":"21_CR17","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, London (1969)"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"Guy, R.K.: Crossing numbers of graphs. In: Proc. Graph Theory and Applications, pp. 111\u2013124. LNM (1972)","DOI":"10.1007\/BFb0067363"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Chojnacki, C., Hanani, H.: \u00dcber wesentlich unpl\u00e4ttbare Kurven im drei-dimensionalen Raume. Fundam. Math. (1934)","DOI":"10.4064\/fm-23-1-135-142"},{"key":"21_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-540-70904-6_17","volume-title":"Graph Drawing","author":"P. Hlin\u011bn\u00fd","year":"2007","unstructured":"Hlin\u011bn\u00fd, P., Salazar, G.: Crossing and weighted crossing number of near-planar graphs. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol.\u00a04372, pp. 162\u2013173. Springer, Heidelberg (2007)"},{"issue":"3","key":"21_CR21","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M.R. Johnson","year":"1983","unstructured":"Johnson, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods\u00a04(3), 312\u2013316 (1983)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"21_CR22","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.jctb.2003.09.002","volume":"92","author":"P. Kolman","year":"2003","unstructured":"Kolman, P., Matousek, J.: Crossing number, pair-crossing number, and expansion. J. Combin. Theory Ser. B\u00a092, 99\u2013113 (2003)","journal-title":"J. Combin. Theory Ser. B"},{"key":"21_CR23","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1006\/jctb.2000.1978","volume":"80","author":"J. Pach","year":"2000","unstructured":"Pach, J., T\u00f3th, G.: Which crossing number is it anyway? Journal of Combinatorial Theory, Series B\u00a080, 225\u2013246 (2000)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"21_CR24","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1002\/jgt.20249","volume":"56","author":"S. Pan","year":"2007","unstructured":"Pan, S., Richter, R.B.: The crossing number of K $_{\\mbox{11}}$ is 100. Journal of Graph Theory\u00a056(2), 128\u2013134 (2007)","journal-title":"Journal of Graph Theory"},{"key":"21_CR25","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.endm.2007.07.015","volume":"29","author":"M.J. Pelsmajer","year":"2007","unstructured":"Pelsmajer, M.J., Schaefer, M., \u0160tefankovi\u010d, D.: Removing even crossings on surfaces. Electronic Notes in Discrete Mathematics\u00a029, 85\u201390 (2007)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"1-3","key":"21_CR26","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1007\/s00454-008-9058-x","volume":"39","author":"M.J. Pelsmajer","year":"2008","unstructured":"Pelsmajer, M.J., Schaefer, M., \u0160tefankovi\u010d, D.: Odd crossing number and crossing number are not the same. Discrete & Computational Geometry\u00a039(1-3), 442\u2013454 (2008)","journal-title":"Discrete & Computational Geometry"},{"key":"21_CR27","unstructured":"The rectilinear crossing number project, http:\/\/dist.ist.tugraz.at\/cape5\/index.php"},{"key":"21_CR28","doi-asserted-by":"publisher","first-page":"939","DOI":"10.2307\/2975158","volume":"101","author":"E.R. Scheinerman","year":"1994","unstructured":"Scheinerman, E.R., Wilf, H.: The rectilinear crossing number of a complete graph and sylvester\u2019s \u201cfour point problem\u201d of geometric probability. American Mathematical Monthly\u00a0101, 939\u2013943 (1994)","journal-title":"American Mathematical Monthly"},{"key":"21_CR29","unstructured":"Spencer, J., Szemer\u00e9di, E., Trotter, W.T.: Unit distances in the euclidean plane. Graph Theory and Combinatorics, 293\u2013308 (1984)"},{"issue":"1-3","key":"21_CR30","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/S0012-365X(03)00317-0","volume":"276","author":"L.A. Sz\u00e9kely","year":"2004","unstructured":"Sz\u00e9kely, L.A.: A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Mathematics\u00a0276(1-3), 331\u2013352 (2004)","journal-title":"Discrete Mathematics"},{"key":"21_CR31","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":"21_CR32","doi-asserted-by":"crossref","unstructured":"Tutte, W.T.: Toward a theory of crossing numbers. Journal of Combinatorial Theory (1970)","DOI":"10.1016\/S0021-9800(70)80007-2"},{"key":"21_CR33","unstructured":"Vrt\u2019o, I.: Bibliography on crossing numbers, ftp:\/\/ftp.ifi.savba.sk\/pub\/imrich\/crobib.pdf"},{"key":"21_CR34","doi-asserted-by":"crossref","unstructured":"Zarankiewicz, K.: On a problem of P. Turan concerning graphs. Fund. Math. (1954)","DOI":"10.4064\/fm-41-1-137-145"}],"container-title":["Lecture Notes in Computer Science","Efficient Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03456-5_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T08:55:46Z","timestamp":1558515346000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03456-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642034558","9783642034565"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03456-5_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}