{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T08:42:12Z","timestamp":1769589732805,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540314257","type":"print"},{"value":"9783540316671","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11618058_4","type":"book-chapter","created":{"date-parts":[[2006,1,20]],"date-time":"2006-01-20T09:56:50Z","timestamp":1137751010000},"page":"37-48","source":"Crossref","is-referenced-by-count":11,"title":["Exact Crossing Minimization"],"prefix":"10.1007","author":[{"given":"Christoph","family":"Buchheim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dietmar","family":"Ebner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"J\u00fcnger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gunnar W.","family":"Klau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ren\u00e9","family":"Weiskircher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0164-1212(84)90006-2","volume":"4","author":"C. Batini","year":"1984","unstructured":"Batini, C., Talamo, M., Tamassia, R.: Computer aided layout of entity-relationship diagrams. Journal of Systems and Software\u00a04, 163\u2013173 (1984)","journal-title":"Journal of Systems and Software"},{"key":"4_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 graph layout problems. Journal of Computer and System Sciences\u00a028, 300\u2013343 (1984)","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR3","unstructured":"Bodlaender, H., Grigoriev, A.: Algorithms for graphs embeddable with few crossings per edge. Research Memoranda 036, Maastricht: METEOR, Maastricht Research School of Economics of Technology and Organization (2004)"},{"issue":"3","key":"4_CR4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences\u00a013(3), 335\u2013379 (1976)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5-6","key":"4_CR5","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0925-7721(96)00005-3","volume":"7","author":"G. Battista Di","year":"1997","unstructured":"Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Computational Geometry: Theory and Applications\u00a07(5-6), 303\u2013325 (1997)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"4","key":"4_CR6","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P. Eades","year":"1994","unstructured":"Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica\u00a011(4), 379\u2013403 (1994)","journal-title":"Algorithmica"},{"key":"4_CR7","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 on Algebraic and Discrete Methods\u00a04, 312\u2013316 (1983)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. In: STOC 2001: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (2001)","DOI":"10.1145\/380752.380805"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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)"},{"key":"4_CR10","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BFb0067363","volume-title":"Graph Theory and Applications (Proceedings)","author":"R.K. Guy","year":"1972","unstructured":"Guy, R.K.: Crossing numbers of graphs. In: Graph Theory and Applications (Proceedings). Lecture Notes in Mathematics, pp. 111\u2013124. Springer, Heidelberg (1972)"},{"issue":"4","key":"4_CR11","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. Journal of the ACM\u00a021(4), 549\u2013568 (1974)","journal-title":"Journal of the ACM"},{"issue":"1","key":"4_CR12","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF02086607","volume":"16","author":"M. J\u00fcnger","year":"1996","unstructured":"J\u00fcnger, M., Mutzel, P.: Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica\u00a016(1), 33\u201359 (1996)","journal-title":"Algorithmica"},{"issue":"1","key":"4_CR13","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. Journal of Combinatorial Theory, Series B\u00a052(1), 67\u201378 (1991)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"4_CR14","unstructured":"Liu, P., Geldmacher, R.: On the deletion of nonplanar edges of a graph. In: Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, pp. 727\u2013738 (1977)"},{"key":"4_CR15","unstructured":"Masuda, S., Kashiwabara, T., Nakajima, K., Fujisawa, T.: On the NP-completeness of a computer network layout problem. In: Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 292\u2013295 (1987)"},{"issue":"1","key":"4_CR16","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1109\/12.46286","volume":"39","author":"S. Masuda","year":"1990","unstructured":"Masuda, S., Nakajima, K., Kashiwabara, T., Fujisawa, T.: Crossing minimization in linear embeddings of graphs. IEEE Transactions on Computers\u00a039(1), 124\u2013127 (1990)","journal-title":"IEEE Transactions on Computers"},{"issue":"3","key":"4_CR17","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(3), 427\u2013439 (1997)","journal-title":"Combinatorica"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/3-540-63938-1_67","volume-title":"Graph Drawing","author":"H.C. Purchase","year":"1997","unstructured":"Purchase, H.C.: Which aesthetic has the greatest effect on human understanding? In: Di Battista, G. (ed.) GD 1997. LNCS, vol.\u00a01353, pp. 248\u2013261. Springer, Heidelberg (1997)"},{"key":"4_CR19","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"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11618058_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:12:19Z","timestamp":1619507539000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11618058_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540314257","9783540316671"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11618058_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}