{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:33:02Z","timestamp":1771036382937,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540877431","type":"print"},{"value":"9783540877448","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-87744-8_24","type":"book-chapter","created":{"date-parts":[[2008,8,30]],"date-time":"2008-08-30T09:20:52Z","timestamp":1220088052000},"page":"284-296","source":"Crossref","is-referenced-by-count":20,"title":["A New Approach to Exact Crossing Minimization"],"prefix":"10.1007","author":[{"given":"Markus","family":"Chimani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Immanuel","family":"Bomze","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"24_CR1","volume-title":"Graph Drawing: algorithms for the visualization of graphs","author":"G. Di Battista","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: algorithms for the visualization of graphs. Prentice-Hall, Englewood Cliffs (1999)"},{"issue":"5-6","key":"24_CR2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0925-7721(96)00005-3","volume":"7","author":"G. Di Battista","year":"1997","unstructured":"Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl.\u00a07(5-6), 303\u2013325 (1997)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"3","key":"24_CR3","doi-asserted-by":"crossref","first-page":"241","DOI":"10.7155\/jgaa.00091","volume":"8","author":"J.M. Boyer","year":"2004","unstructured":"Boyer, J.M., Myrvold, W.J.: On the cutting edge: Simplified O(n) planarity by edge addition. Journal of Graph Algorithms an Applications\u00a08(3), 241\u2013273 (2004)","journal-title":"Journal of Graph Algorithms an Applications"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/j.disopt.2007.05.006","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\u00a05, 373\u2013388 (2008); (Memory of George B. Dantzig)","journal-title":"Discrete Optimization"},{"key":"24_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/11809678_52","volume-title":"Computing and Combinatorics","author":"C. Buchheim","year":"2006","unstructured":"Buchheim, C., J\u00fcnger, M., Menze, A., Percan, M.: Bimodal crossing minimization. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol.\u00a04112, pp. 497\u2013506. Springer, Heidelberg (2006)"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-540-77120-3_18","volume-title":"Algorithms and Computation","author":"M. Chimani","year":"2007","unstructured":"Chimani, M., Gutwenger, C.: Algorithms for the hypergraph and the minor crossing number problems. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 184\u2013195. Springer, Heidelberg (2007)"},{"key":"24_CR7","series-title":"Lecture Notes in Computer Science","first-page":"223","volume-title":"Graph Drawing","author":"M. Chimani","year":"2006","unstructured":"Chimani, M., Gutwenger, C.: Non-planar core reduction of graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol.\u00a03843, pp. 223\u2013234. Springer, Heidelberg (2006)"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/11764298_28","volume-title":"Experimental Algorithms","author":"M. Chimani","year":"2006","unstructured":"Chimani, M., Gutwenger, C., Mutzel, P.: Experiments on exact crossing minimization using column generation. In: \u00c0lvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol.\u00a04007, pp. 303\u2013315. Springer, Heidelberg (2006)"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Chimani, M., J\u00fcnger, M., Schulz, M.: Crossing minimization meets simultaneous drawing. In: Proc. IEEE PacificVis 2008 (2008)","DOI":"10.1109\/PACIFICVIS.2008.4475456"},{"key":"24_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-540-77537-9_17","volume-title":"Graph Drawing","author":"M. Chimani","year":"2008","unstructured":"Chimani, M., Mutzel, P., Schmidt, J.M.: Efficient extraction of multiple kuratowski subdivisions. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol.\u00a04875, pp. 159\u2013170. Springer, Heidelberg (2008)"},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/978-3-540-24595-7_2","volume-title":"Graph Drawing","author":"C. Gutwenger","year":"2004","unstructured":"Gutwenger, C., Mutzel, P.: An experimental study of crossing minimization heuristics. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 13\u201324. Springer, Heidelberg (2004)"},{"issue":"4","key":"24_CR12","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":"24_CR13","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 K\n                  5,n\n                  . J. Comb. Theory\u00a09, 315\u2013323 (1970)","journal-title":"J. Comb. Theory"},{"issue":"1","key":"24_CR14","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/0095-8956(76)90032-0","volume":"21","author":"D.J. Kleitman","year":"1976","unstructured":"Kleitman, D.J.: A note on the parity of the number of crossings of a graph. J. Comb. Theory, Ser. B\u00a021(1), 88\u201389 (1976)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0095-8956(91)90091-W","volume":"52","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J.: String graphs II: Recognizing string graphs is NP-hard. J. Combin. Theory Ser. B\u00a052, 67\u201378 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"key":"24_CR16","doi-asserted-by":"crossref","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","volume":"15","author":"C. Kuratowski","year":"1930","unstructured":"Kuratowski, C.: Sur le probl\u00e8me des courbes gauches en topologie. Fund. Math.\u00a015, 271\u2013283 (1930)","journal-title":"Fund. Math."},{"key":"24_CR17","unstructured":"OGDF \u2013 Open Graph Drawing Framework (2008), \n                      http:\/\/www.ogdf.net"},{"issue":"2","key":"24_CR18","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? J. Comb. Theory Ser. B\u00a080(2), 225\u2013246 (2000)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"24_CR19","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0022-0000(03)00045-X","volume":"67","author":"M. Schaefer","year":"2003","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Recognizing string graphs in NP. Journal of Computer and System Sciences\u00a067(2), 365\u2013380 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR20","unstructured":"Vrt\u2019o, I.: Crossing numbers of graphs: A bibliography (2007), \n                      ftp:\/\/ftp.ifi.savba.sk\/pub\/imrich\/crobib.pdf"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2008"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87744-8_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T05:16:34Z","timestamp":1715058994000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-87744-8_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540877431","9783540877448"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87744-8_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}