{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T13:09:48Z","timestamp":1758632988935},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424932"},{"type":"electronic","value":"9783540446767"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44676-1_41","type":"book-chapter","created":{"date-parts":[[2007,5,18]],"date-time":"2007-05-18T12:43:15Z","timestamp":1179492195000},"page":"488-499","source":"Crossref","is-referenced-by-count":17,"title":["On the Parameterized Complexity of Layered Graph Drawing"],"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":"G.","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":"D. R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"issue":"1","key":"41_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. S. Baker","year":"1994","unstructured":"B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. ACM, 41(1):153\u2013180, 1994.","journal-title":"J. ACM"},{"key":"41_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/3-540-44541-2_22","volume-title":"Proc. Graph Drawing: 8th International Symposium (GD\u201900)","author":"C. Buchheim","year":"2001","unstructured":"C. Buchheim, M. J\u00fcnger, and S. Leipert. A fast layout algorithm for k-level graphs. In J. Marks, editor, Proc. Graph Drawing: 8th International Symposium (GD\u201900), volume 1984 of Lecture Notes in Comput. Sci., pages 229\u2013240. Springer, 2001."},{"key":"41_CR3","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF01840379","volume":"5","author":"D. Bienstock","year":"1990","unstructured":"D. Bienstock and C. L. Monma. On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmics, 5:93\u2013109, 1990.","journal-title":"Algorithmics"},{"issue":"6","key":"41_CR4","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. L. Bodlaender","year":"1996","unstructured":"H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305\u20131317, 1996.","journal-title":"SIAM Journal on Computing"},{"issue":"11","key":"41_CR5","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":"41_CR6","unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999."},{"key":"41_CR7","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. Parameterized complexity. Springer, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"41_CR8","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. Submitted."},{"key":"41_CR9","doi-asserted-by":"crossref","unstructured":"P. Eades, Q. W. Feng, and X. Lin. Straight-line drawing algorithms for hierarchical graphs and clustered graphs. In [25], pages 113\u2013128.","DOI":"10.1007\/3-540-62495-3_42"},{"issue":"2","key":"41_CR10","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":"41_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":"41_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"},{"key":"41_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/3-540-44985-X_11","volume-title":"Proc. 7th Scandinavian Workshop on Algorithm Theory (SWAT\u201900)","author":"A. Gupta","year":"2000","unstructured":"A. Gupta, N. Nishimura, A. Proskurowski, and P. Ragde. Embeddings of k- connected graphs of pathwidth k. In M. M. Halldorsson, editor, Proc. 7th Scandinavian Workshop on Algorithm Theory (SWAT\u201900), volume 1851 of Lecture Notes in Comput. Sci., pages 111\u2013124. Springer, 2000."},{"key":"41_CR14","doi-asserted-by":"crossref","unstructured":"M. Grohe. Computing crossing numbers in quadratic time. In Proc. 32nd Annual ACM Symposium on Theory of Computing (STOC\u201901), 2001. To appear.","DOI":"10.1145\/380752.380805"},{"key":"41_CR15","unstructured":"P. Healy and A. Kuusik. The vertex-exchange graph and its use in multi-level graph layout. In [20], pages 205\u2013216."},{"key":"41_CR16","doi-asserted-by":"crossref","unstructured":"M. J\u00fcnger and S. Leipert. Level planar embedding in linear time. In [20], pages 72\u201381.","DOI":"10.1007\/3-540-46648-7_7"},{"key":"41_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/3-540-37623-2_17","volume-title":"Proc. Graph Drawing: 6th International Symposium (GD\u201998)","author":"M. J\u00fcnger","year":"1998","unstructured":"M. J\u00fcnger, S. Leipert, and P. Mutzel. Level planarity testing in linear time. In S. Whitesides, editor, Proc. Graph Drawing: 6th International Symposium (GD\u201998), volume 1547 of Lecture Notes in Comput. Sci., pages 224\u2013237. Springer, 1998."},{"key":"41_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-63938-1_46","volume-title":"Proc. Graph Drawing: 5th International Symposium (GD\u201997)","author":"M. J\u2019unger","year":"1998","unstructured":"M. J\u2019unger, E. Lee, P. Mutzel, and T. Odenthal. A polyhedral approach to the multi-layer crossing minimization problem. In G. Di Battista, editor, Proc. Graph Drawing: 5th International Symposium (GD\u201997), volume 1353 of Lecture Notes in Comput. Sci., pages 13\u201324. Springer, 1998."},{"issue":"1","key":"41_CR19","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":"41_CR20","series-title":"Lect Notes Comput Sci","volume-title":"Proc. Graph Drawing: 7th International Symposium (GD\u201999)","year":"1999","unstructured":"J. Kratochvil, editor. Proc. Graph Drawing: 7th International Symposium (GD\u201999), volume 1731 of Lecture Notes in Comput. Sci. Springer, 1999."},{"key":"41_CR21","doi-asserted-by":"crossref","unstructured":"T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. John Wiley, 1990.","DOI":"10.1007\/978-3-322-92106-2_3"},{"key":"41_CR22","doi-asserted-by":"crossref","unstructured":"P. Mutzel. An alternative method to crossing minimization on hierarchical graphs. In [25], pages 318\u2013333. To appear in SIAM Journal on Optimization.","DOI":"10.1007\/3-540-62495-3_57"},{"key":"41_CR23","doi-asserted-by":"crossref","unstructured":"P. Mutzel. Optimization in leveled graphs. In P. M. Pardalos and C. A. Floudas, editors, Encyclopedia of Optimization. Kluwer, 2001. To appear.","DOI":"10.1007\/0-306-48332-7_365"},{"key":"41_CR24","series-title":"Lect Notes Comput Sci","first-page":"69","volume-title":"Proc. 9th International Symposium on Algorithms and Computation (ISAAC\u201998)","author":"P. Mutzel","year":"1998","unstructured":"P. Mutzel and R. Weiskircher. Two-layer planarization in graph drawing. In K. Y. Chwa and O. H. Ibarra, editors, Proc. 9th International Symposium on Algorithms and Computation (ISAAC\u201998), volume 1533 of Lecture Notes in Comput. Sci., pages 69\u201378. Springer, 1998."},{"key":"41_CR25","series-title":"Lect Notes Comput Sci","volume-title":"Proc. Graph Drawing: Symposium on Graph Drawing (GD\u201996)","year":"1997","unstructured":"S. North, editor. Proc. Graph Drawing: Symposium on Graph Drawing (GD\u201996), volume 1190 of Lecture Notes in Comput. Sci. Springer, 1997."},{"issue":"2","key":"41_CR26","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":"41_CR27","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"},{"issue":"7","key":"41_CR28","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."},{"issue":"2","key":"41_CR29","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","Algorithms \u2014 ESA 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44676-1_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T00:43:57Z","timestamp":1556412237000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44676-1_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424932","9783540446767"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-44676-1_41","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}