{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:30:11Z","timestamp":1725489011351},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540433095"},{"type":"electronic","value":"9783540458487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45848-4_1","type":"book-chapter","created":{"date-parts":[[2007,8,11]],"date-time":"2007-08-11T10:47:53Z","timestamp":1186829273000},"page":"1-15","source":"Crossref","is-referenced-by-count":9,"title":["A Fixed-Parameter Approach to Two-Layer Planarization"],"prefix":"10.1007","author":[{"given":"V.","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Hallett","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Kitching","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"McCartin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Ragde","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Suderman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Whitesides","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"1_CR1","unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999."},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. Parametrized complexity. Springer, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"1_CR3","unstructured":"V. Dujmovi\u0107, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosemand, M. Suderman, S. Whitesides, and D. R. Wood. On the parameterized complexity of layered graph drawing. In Proc. 9th European Symp. on Algorithms (ESA\u2019 01), to appear."},{"key":"1_CR4","unstructured":"P. Eades, B. D. McKay, and N. C. Wormald. On an edge crossing problem. In Proc. 9th Australian Computer Science Conference, pages 327\u2013334. Australian National University, 1986."},{"issue":"2","key":"1_CR5","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. Theoret. Comput. Sci., 131(2):361\u2013374, 1994.","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1_CR6","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P. Eades","year":"1994","unstructured":"P. Eades and N. C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11(4):379\u2013403, 1994.","journal-title":"Algorithmica"},{"issue":"3","key":"1_CR7","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(3):312\u2013316, 1983.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"1_CR8","first-page":"203","volume":"1","author":"F. Harary","year":"1972","unstructured":"F. Harary and A. Schwenk. A new crossing number for bipartite graphs. Utilitas Math., 1:203\u2013209, 1972.","journal-title":"Utilitas Math."},{"issue":"1","key":"1_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00001","volume":"1","author":"M. J\u00fcnger","year":"1997","unstructured":"M. J\u00fcnger and P. Mutzel. 2-layer straightline crossing minimization: performance of exact and heuristic algorithms. J. Graph Algorithms Appl., 1(1):1\u201325, 1997.","journal-title":"J. Graph Algorithms Appl."},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"M. Kaufmann and D. Wagner, editors. Drawing Graphs: Methods and Models, volume 2025 of Lecture Notes in Comput. Sci. Springer, 2001.","DOI":"10.1007\/3-540-44969-8"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, 1990.","DOI":"10.1007\/978-3-322-92106-2_3"},{"issue":"4","key":"1_CR12","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1137\/S1052623498334013","volume":"11","author":"P. Mutzel","year":"2001","unstructured":"P. Mutzel. An alternative method to crossing minimization on hierarchical graphs. SIAM J. Optimization, 11(4):1065\u20131080, 2001.","journal-title":"SIAM J. Optimization"},{"key":"1_CR13","unstructured":"P. Mutzel. Optimization in leveled graphs. In P. M. Pardalos and C. A. Floudas, editors, Encyclopedia of Optimization. Kluwer, to appear."},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"P. Mutzel and R. Weiskircher. Two-layer planarization in graph drawing. In K. Y. Chwa and O. H. Ibarra, editors, Proc. 9th International Symp. on Algorithms and Computation (ISAAC\u201998), volume 1533 of Lecture Notes in Comput. Sci., pages 69\u201378. Springer, 1998.","DOI":"10.1007\/3-540-49381-6_9"},{"issue":"6","key":"1_CR15","doi-asserted-by":"publisher","first-page":"1773","DOI":"10.1137\/S0097539797331671","volume":"30","author":"F. Shahrokhi","year":"2001","unstructured":"F. Shahrokhi, O. S\u00fdkora, L. A. Sz\u00e9kely, and I. Vr\u0165o. On bipartite drawings and the linear arrangement problem. SIAM J. Comput., 30(6):1773\u20131789, 2001.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1_CR16","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. Methods for visual understanding of hierarchical system structures. Trans. Systems Man Cybernet., 11(2):109\u2013125, 1981.","journal-title":"Trans. Systems Man Cybernet."},{"key":"1_CR17","unstructured":"N. Tomii, Y. Kambayashi, and S. Yajima. On planarization algorithms of 2-level graphs. Papers of tech. group on elect. comp., IECEJ, EC77-38:1\u201312, 1977."},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0377-2217(95)00356-8","volume":"90","author":"V. Valls","year":"1996","unstructured":"V. Valls, R. Marti, and P. Lino. A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs. J. Operat. Res., 90:303\u2013319, 1996.","journal-title":"J. Operat. Res."},{"issue":"2","key":"1_CR19","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02460022","volume":"48","author":"M. S. Waterman","year":"1986","unstructured":"M. S. Waterman and J. R. Griggs. Interval graphs and maps of DNA. Bull. Math. Biol., 48(2):189\u2013195, 1986.","journal-title":"Bull. Math. Biol."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45848-4_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T19:28:24Z","timestamp":1556738904000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45848-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540433095","9783540458487"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-45848-4_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}