{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T05:38:11Z","timestamp":1769578691276,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540208310","type":"print"},{"value":"9783540245957","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24595-7_2","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T08:46:01Z","timestamp":1280393161000},"page":"13-24","source":"Crossref","is-referenced-by-count":22,"title":["An Experimental Study of Crossing Minimization Heuristics"],"prefix":"10.1007","author":[{"given":"Carsten","family":"Gutwenger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"2_CR1","doi-asserted-by":"publisher","first-page":"956","DOI":"10.1137\/S0097539794280736","volume":"25","author":"G. Battista Di","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM Journal on Computing\u00a025(5), 956\u2013997 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"2_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":"2_CR3","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/BF02574701","volume":"6","author":"D. Bienstock","year":"1991","unstructured":"Bienstock, D.: Some provablyhard crossing number problems. Discrete & Computational Geometry\u00a06, 443\u2013459 (1991)","journal-title":"Discrete & Computational Geometry"},{"key":"2_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/BFb0021792","volume-title":"Graph Drawing","author":"F.J. Brandenburg","year":"1996","unstructured":"Brandenburg, F.J., Himsolt, M., Rohrer, C.: An experimental comparison of force-directed and randomized graph drawing algorithms. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol.\u00a01027, pp. 76\u201387. Springer, Heidelberg (1996)"},{"issue":"1","key":"2_CR5","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/0022-0000(85)90004-2","volume":"30","author":"N. Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T., Abe, S., Ozawa, T.: A linear algorithm for embedding planar graphs using PQ-trees. J. Comput. Syst. Sci.\u00a030(1), 54\u201376 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR6","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. Comput. Geom. Theory Appl.\u00a07, 303\u2013326 (1997)","journal-title":"Comput. Geom. Theory Appl."},{"key":"2_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/3-540-36151-0_27","volume-title":"Graph Drawing","author":"T. Eschbach","year":"2002","unstructured":"Eschbach, T., G\u00fcnther, W., Drechsler, R., Becker, B.: Crossing reduction by windows optimization. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol.\u00a02528, pp. 285\u2013294. Springer, Heidelberg (2002)"},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1145\/335305.335340","volume-title":"Proc. 32nd ACM Symp. Theory of Comp. (STOC 2000)","author":"G. Even","year":"2000","unstructured":"Even, G., Guha, S., Schieber, B.: Improved approximations of crossings in graph drawing and VLSI layout area. In: Proc. 32nd ACM Symp. Theory of Comp. (STOC 2000), pp. 296\u2013305. ACM Press, New York (2000)"},{"key":"2_CR9","first-page":"231","volume-title":"Proc. 32nd ACM Symp. Theory of Computing (STOC 2000)","author":"M. Grohe","year":"2000","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. In: Proc. 32nd ACM Symp. Theory of Computing (STOC 2000), pp. 231\u2013236. ACM Press, New York (2000)"},{"key":"2_CR10","unstructured":"Gutwenger, C., Klein, K., Kupke, J., Leipert, S., J\u00fcnger, M., Mutzel, P.: Govisual software tools (2002), http:\/\/www.oreas.de"},{"key":"2_CR11","first-page":"246","volume-title":"Proc. Ninth Ann. ACM-SIAM Symp. Discr. Algorithms (SODA 2001)","author":"C. Gutwenger","year":"2001","unstructured":"Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. In: Proc. Ninth Ann. ACM-SIAM Symp. Discr. Algorithms (SODA 2001), Washington, DC, pp. 246\u2013255. ACM Press, New York (2001)"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1109\/43.21845","volume":"8","author":"R. Jayakumar","year":"1989","unstructured":"Jayakumar, R., Thulasiraman, K., Swamy, M.N.S.: O(n 2) algorithms for graph planarization. IEEE Trans. on Computer-Aided Design\u00a08, 257\u2013267 (1989)","journal-title":"IEEE Trans. on Computer-Aided Design"},{"issue":"3","key":"2_CR13","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":"2_CR14","doi-asserted-by":"crossref","unstructured":"J\u00fcnger, M., Leipert, S., Mutzel, P.: A note on computing a maximal planar subgraph using PQ-trees. IEEE Trans. Computer-Aided Design\u00a017(7) (1998)","DOI":"10.1109\/43.709399"},{"issue":"1","key":"2_CR15","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":"2_CR16","first-page":"1","volume":"1","author":"M. J\u00fcnger","year":"1997","unstructured":"J\u00fcnger, M., Mutzel, P.: 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. J. Gr. Alg. & Appl. (JGAA)\u00a01(1), 1\u201325 (1997)","journal-title":"J. Gr. Alg. & Appl. (JGAA)"},{"issue":"6","key":"2_CR17","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"F.T. Leighton","year":"1999","unstructured":"Leighton, F.T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM\u00a046(6), 787\u2013832 (1999)","journal-title":"J. ACM"},{"key":"2_CR18","unstructured":"Liu, P.C., Geldmacher, R.C.: On the deletion of nonplanar edges of a graph. In: 10th. S-E Conf. Comb., Graph Theory, and Comp., pp. 727\u2013738 (1977)"},{"issue":"2","key":"2_CR19","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF01940648","volume":"16","author":"K. Mehlhorn","year":"1996","unstructured":"Mehlhorn, K., Mutzel, P.: On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. Algorithmica\u00a016(2), 233\u2013242 (1996)","journal-title":"Algorithmica"},{"key":"2_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/3-540-46648-7_18","volume-title":"Graph Drawing","author":"P. Mutzel","year":"1999","unstructured":"Mutzel, P., Ziegler, T.: The constrained crossing min. problem. In: Kratochv\u00edl, J. (ed.) GD 1999. LNCS, vol.\u00a01731, pp. 175\u2013185. Springer, Heidelberg (1999)"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"La Poutr\u00e9, J.A.: Alpha-algorithms for incremental planaritytesting. In: Proc. 26th Annual ACM Symp. Theory of Computation (STOC), pp. 706\u2013715 (1994)","DOI":"10.1145\/195058.195439"},{"key":"2_CR22","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. Purchase","year":"1997","unstructured":"Purchase, H.: Which aesthetic has the greatest effect on human understanding? In: DiBattista, G. (ed.) GD 1997. LNCS, vol.\u00a01353, pp. 248\u2013261. Springer, Heidelberg (1997)"},{"key":"2_CR23","doi-asserted-by":"crossref","unstructured":"Richter, R.B., Thomassen, C.: Relations between crossing numbers of complete and complete bipartite graphs. In: Amer. Math. Monthly, pp. 131\u2013137 (1997)","DOI":"10.1080\/00029890.1997.11990611"},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1002\/1097-024X(200009)30:11<1235::AID-SPE339>3.0.CO;2-B","volume":"30","author":"L. Vismara","year":"2000","unstructured":"Vismara, L., Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Vargiu, F.: Experimental studies on graph drawing algorithms. Software \u2013 Practice and Experience\u00a030, 1235\u20131284 (2000)","journal-title":"Software \u2013 Practice and Experience"},{"key":"2_CR25","unstructured":"Ziegler, T.: Crossing Minimization in Automatic Graph Drawing. PhD thesis, Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken (2000)"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24595-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T23:53:26Z","timestamp":1559346806000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24595-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540208310","9783540245957"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24595-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}