{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:39Z","timestamp":1759638519899},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540001584"},{"type":"electronic","value":"9783540361510"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36151-0_12","type":"book-chapter","created":{"date-parts":[[2007,11,16]],"date-time":"2007-11-16T17:14:14Z","timestamp":1195233254000},"page":"118-129","source":"Crossref","is-referenced-by-count":3,"title":["An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization"],"prefix":"10.1007","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sue","family":"Whitesides","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,11,8]]},"reference":[{"issue":"11","key":"12_CR1","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1109\/TSMC.1980.4308390","volume":"SMC-10","author":"M. J. Carpano","year":"1980","unstructured":"M. J. Carpano. Automatic display of hierarchized graphs for computer aided decision analysis. IEEE Trans. Syst. Man Cybern., SMC-10(11):705\u2013715, 1980.","journal-title":"IEEE Trans. Syst. Man Cybern"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"C. Catarci. The assignment heuristic for crossing reduction. IEEE Trans. on Systems, Man, and Cybernetics, 25(3), 1995.","DOI":"10.1109\/21.364865"},{"key":"12_CR3","unstructured":"T. Corman, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, 1990."},{"key":"12_CR4","unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999."},{"key":"12_CR5","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":"12_CR6","doi-asserted-by":"crossref","unstructured":"S. Dresbach. A new heuristic layout algorithm for directed acyclic graphs. In U. Derigs, A. Bachem, and A. B. A. Drexl, editors, Operations Research Proceedings (1994), pages 121\u2013126. Springer, 1995.","DOI":"10.1007\/978-3-642-79459-9_23"},{"key":"12_CR7","doi-asserted-by":"crossref","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. A fixed-parameter approach to two-layer planarization. In Mutzel [15], pages 1\u201315.","DOI":"10.1007\/3-540-45848-4_1"},{"key":"12_CR8","doi-asserted-by":"crossref","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 parameterizedcomplexit y of layeredgraph drawing. In Proc. 9th European Symposium on Algorithms (ESA 2001), volume 2161 of Lecture Notes in Comput. Sci., pages 488\u2013499. Springer, 2001.","DOI":"10.1007\/3-540-44676-1_41"},{"issue":"A","key":"12_CR9","first-page":"89","volume":"21","author":"P. Eades","year":"1986","unstructured":"P. Eades and D. Kelly. Heuristics for drawing 2-layered networks. Ars Combin., 21(A):89\u201398, 1986.","journal-title":"Ars Combin"},{"issue":"2","key":"12_CR10","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0304-3975(94)90179-1","volume":"131","author":"E. P","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":"12_CR11","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":"12_CR12","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"},{"issue":"1","key":"12_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00001","volume":"1","author":"J. M","year":"1997","unstructured":"M. J\u00fcnger and P. Mutzel. 2-layer straightline crossing minimization: performance of exact andheuristic algorithms. J. Graph Algorithms Appl., 1(1):1\u201325, 1997.","journal-title":"J. Graph Algorithms Appl"},{"key":"12_CR14","unstructured":"X Mu\u00f1oz, U Unger, and I Vr\u0165o. One sidedcrossing minimization is np-hardfor sparse graphs. In Mutzel [15]. to appear."},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"P. Mutzel, editor. Proc. Graph Drawing: 9th International Symposium (GD\u201901), volume 2265 of Lecture Notes in Comput. Sci. Springer, 2001.","DOI":"10.1007\/3-540-45848-4"},{"issue":"2","key":"12_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. IEEE Trans. Systems Man Cybernet., 11(2):109\u2013125, 1981.","journal-title":"IEEE Trans. Systems Man Cybernet"},{"key":"12_CR17","first-page":"1","volume":"EC77-38","author":"N. Tomii","year":"1977","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.","journal-title":"Papers of tech. group on elect. comp., IECEJ"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0377-2217(95)00356-8","volume":"90","author":"V. V","year":"1996","unstructured":"V. Valls, R. Marti, and P. Lino. A branch andb oundalgorithm for minimizing the number of crossing arcs in bipartite graphs. J. Operational Res., 90:303\u2013319, 1996.","journal-title":"J. Operational Res"},{"issue":"7","key":"12_CR19","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1109\/TSMC.1977.4309760","volume":"SMC-7","author":"J. N. Warfield","year":"1977","unstructured":"J. N. Warfield. Crossing theory and hierarchy mapping. IEEE Trans. Systems Man Cybernet., SMC-7(7):505\u2013523, 1977.","journal-title":"IEEE Trans. Systems Man Cybernet"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36151-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,28]],"date-time":"2020-04-28T06:54:12Z","timestamp":1588056852000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36151-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540001584","9783540361510"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-36151-0_12","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}