{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T04:16:05Z","timestamp":1754194565183},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540653851"},{"type":"electronic","value":"9783540493815"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49381-6_9","type":"book-chapter","created":{"date-parts":[[2007,12,3]],"date-time":"2007-12-03T06:47:50Z","timestamp":1196664470000},"page":"72-79","source":"Crossref","is-referenced-by-count":7,"title":["Two-Layer Planarization in Graph Drawing"],"prefix":"10.1007","author":[{"given":"Petra","family":"Mutzel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ren\u00e9","family":"Weiskircher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,3,29]]},"reference":[{"key":"9_CR1","unstructured":"G. D. Battista, A. Garg, G. Liotta, A. Parise, R. Tamassia, E. Tassinari, F. Vargiu, and L. Vismara. Drawing directed acyclic graphs: An experimental study (preliminary version). Technical Report CS-96-24, Department of Computer Science, Brown University, Oct. 1996. Sun, 13 Jul 1997 18:30:15 GMT."},{"issue":"11","key":"9_CR2","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1109\/TSMC.1980.4308390","volume":"10","author":"M. Carpano","year":"1980","unstructured":"M. Carpano. Automatic display of hierarchized graphs for computer aided decision analysis. IEEE Trans. on Systems, Man and Cybernetics, SMC-10(11):705\u2013715, 1980.","journal-title":"IEEE Trans. on Systems, Man and Cybernetics"},{"key":"9_CR3","first-page":"89","volume":"21-A","author":"P. Eades","year":"1986","unstructured":"P. Eades and D. Kelly. Heuristics for reducing crossings in 2-layered networks. Ars Combinatoria, 21-A:89\u201398, 1986.","journal-title":"Ars Combinatoria"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0304-3975(94)90179-1","volume":"131","author":"P. Eades","year":"1994","unstructured":"P. Eades and S. Whitesides. Drawing graphs in two layers. Theoretical Computer Science 131, pages 361\u2013374, 1994.","journal-title":"Theoretical Computer Science"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01187020","volume":"10","author":"P. Eades","year":"1994","unstructured":"P. Eades and N. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 10:379\u2013403, 1994.","journal-title":"Algorithmica"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M. R. Garey","year":"1983","unstructured":"M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods, 4:312\u2013316, 1983.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"9_CR7","doi-asserted-by":"crossref","first-page":"1195","DOI":"10.1287\/opre.32.6.1195","volume":"32","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"M. Gr\u00f6tschel, M. J\u00fcnger, and G. Reinelt. A cutting plane algorithm for the linear ordering problem. Operations Research, 32:1195\u20131220, 1984.","journal-title":"Operations Research"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Shrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169\u2013197, 1981.","journal-title":"Combinatorica"},{"key":"9_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BFb0021817","volume-title":"Graph Drawing (Proc. GD\u2019 95)","author":"M. J\u00fcnger","year":"1996","unstructured":"M. J\u00fcnger and P. Mutzel. Exact and heuristic algorithms for 2-layer straightline crossing minimization. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD\u2019 95), volume 1027 of LNCS, pages 337\u2013348, 1996."},{"key":"9_CR10","unstructured":"M. J\u00fcnger and S. Thienel. The design of the branch and cut system ABACUS. Tech. Rep. No. 97.260, Institut f\u00fcr Informatik, Universit\u00e4t zu K\u00f6ln, 1997."},{"key":"9_CR11","series-title":"Lect Notes Comput Sci","volume-title":"Proc. Graph Drawing\u2019 96","author":"P. Mutzel","year":"1997","unstructured":"P. Mutzel. An alternative approach for drawing hierarchical graphs. Proc. Graph Drawing\u2019 96, LNCS, 1997. to appear."},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/BF01580222","volume":"6","author":"G. L. Nemhauser","year":"1973","unstructured":"G. L. Nemhauser and L. E. Trotter. Properties of vertex packing and independence system polyhedra. Mathematical Programming, 6:48\u201361, 1973.","journal-title":"Mathematical Programming"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"K. Reinert, H. P. Lenhof, P. Mutzel, K. Mehlhorn, and J. Kececioglu. A branch-and-cut algorithm for multiple sequence alignment. In Proc. of the 1st Ann. Intern. Conf. on Comp. Molec. Bio. (RECOMB 97), Santa Fe, NM, 1997.","DOI":"10.1145\/267521.267845"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K. Sugiyama","year":"1981","unstructured":"K. Sugiyama, S. Tagawa, and M. Toda. On planarization algorithms of 2-level graphs. IEEE Trans. on Systems, Man and Cybernetics, SMC-11:109\u2013125, 1981.","journal-title":"IEEE Trans. on Systems, Man and Cybernetics"},{"key":"9_CR15","unstructured":"N. Tomii, Y. Kambayashi, and S. Yajima. On planarization algorithms of 2-level graphs. Papers of tech. group on electronic computers, IECEJ, EC77-38, pages 1\u201312, 1977."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49381-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,26]],"date-time":"2019-02-26T05:26:34Z","timestamp":1551158794000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49381-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540653851","9783540493815"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-49381-6_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}