{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T15:55:23Z","timestamp":1770738923881,"version":"3.49.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,12,7]],"date-time":"2007-12-07T00:00:00Z","timestamp":1196985600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s00453-007-9151-1","type":"journal-article","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T17:58:19Z","timestamp":1196963899000},"page":"267-292","source":"Crossref","is-referenced-by-count":40,"title":["On the Parameterized Complexity of Layered Graph Drawing"],"prefix":"10.1007","volume":"52","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Kitching","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Catherine","family":"McCartin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naomi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prabhakar","family":"Ragde","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sue","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":[[2007,12,7]]},"reference":[{"issue":"1","key":"9151_CR1","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"9151_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/3-540-44541-2_22","volume-title":"Proc. Graph Drawing: 8th Internat. Symp. (GD\u201900)","author":"C. Buchheim","year":"2001","unstructured":"Buchheim, C., J\u00fcnger, M., Leipert, S.: A fast layout algorithm for k-level graphs. In: Marks, J. (ed.) Proc. Graph Drawing: 8th Internat. Symp. (GD\u201900). Lecture Notes in Computer Science, vol. 1984, pp. 229\u2013240. Springer, New York (2001)"},{"key":"9151_CR3","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21, 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"key":"9151_CR4","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/BF01840379","volume":"5","author":"D. Bienstock","year":"1990","unstructured":"Bienstock, D., Monma, C.L.: On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmics 5, 93\u2013109 (1990)","journal-title":"Algorithmics"},{"issue":"6","key":"9151_CR5","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"11","key":"9151_CR6","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1109\/TSMC.1980.4308390","volume":"10","author":"M.J. Carpano","year":"1980","unstructured":"Carpano, M.J.: Automatic display of hierarchized graphs for computer aided decision analysis. IEEE Trans. Syst. Man Cybern. 10(11), 705\u2013715 (1980)","journal-title":"IEEE Trans. Syst. Man Cybern."},{"issue":"2","key":"9151_CR7","doi-asserted-by":"crossref","first-page":"161","DOI":"10.7155\/jgaa.00087","volume":"8","author":"S. Cornelsen","year":"2004","unstructured":"Cornelsen, S., Schank, T., Wagner, D.: Drawing graphs on two and three lines. J. Graph. Algorithms Appl. 8(2), 161\u2013177 (2004)","journal-title":"J. Graph. Algorithms Appl."},{"key":"9151_CR8","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G. Di Battista","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, New York (1999)"},{"key":"9151_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9151_CR10","doi-asserted-by":"crossref","unstructured":"Dujmovi\u0107, V., Fellows, M., Hallett, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde,\u00a0P., Rosamond, F., Suderman, M., Whitesides, S., Wood, D.R.: On the parameterized complexity of layered graph drawing. In: Meyer auf der Heide, F. (ed.) European Symposium on Algorithms, pp.\u00a0488\u2013499 (2001)","DOI":"10.1007\/3-540-44676-1_41"},{"key":"9151_CR11","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Proc. 9th Internat. Symp. on Graph Drawing (GD \u201901)","author":"V. Dujmovi\u0107","year":"2002","unstructured":"Dujmovi\u0107, V., Fellows, M., Hallett, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde,\u00a0P., Rosamond, F., Suderman, M., Whitesides, S., Wood, D.R.: A fixed-parameter approach to two-layer planarization. In: Mutzel, P., J\u00fcnger, M., Leipert, S. (eds.) Proc. 9th Internat. Symp. on Graph Drawing (GD \u201901). Lecture Notes in Computer Science, vol. 2265, pp. 1\u201315. Springer, New York (2002)"},{"issue":"2","key":"9151_CR12","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s00453-005-1181-y","volume":"45","author":"V. Dujmovi\u0107","year":"2006","unstructured":"Dujmovi\u0107, V., Fellows, M., Hallett, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde,\u00a0P., Rosamond, F., Suderman, M., Whitesides, S., Wood, D.R.: A fixed-parameter approach to two-layer planarization. Algorithmica 45(2), 159\u2013182 (2006)","journal-title":"Algorithmica"},{"key":"9151_CR13","author":"V. Dujmovi\u0107","year":"2007","unstructured":"Dujmovi\u0107, V., Fernau, H., Kaufmann, M.: Fixed parameter algorithms for one-sided crossing minimization revisited. J. Discrete Algorithms (2007). doi: 10.1016\/j.jda.2006.12.008","journal-title":"J. Discrete Algorithms"},{"key":"9151_CR14","series-title":"Graduate Texts in Mathematics","volume-title":"Graph theory","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph theory, 2nd edn. Graduate Texts in Mathematics, vol.\u00a0173. Springer, New York (2000)","edition":"2"},{"issue":"3","key":"9151_CR15","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1137\/S0097539702416141","volume":"34","author":"V. Dujmovi\u0107","year":"2005","unstructured":"Dujmovi\u0107, V., Morin, P., Wood, D.R.: Layout of graphs with bounded tree-width. SIAM J. Comput. 34(3), 553\u2013579 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9151_CR16","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/s00453-004-1093-2","volume":"40","author":"V. Dujmovi\u0107","year":"2004","unstructured":"Dujmovi\u0107, V., Whitesides, S.: An efficient fixed parameter tractable algorithm for 1-sided crossing minimization. Algorithmica 40(1), 15\u201331 (2004)","journal-title":"Algorithmica"},{"issue":"2","key":"9151_CR17","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/0304-3975(94)90179-1","volume":"131","author":"P. Eades","year":"1994","unstructured":"Eades, P., Whitesides, S.: Drawing graphs in two layers. Theor. Comput. Sci. 131(2), 361\u2013374 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9151_CR18","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P. Eades","year":"1994","unstructured":"Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4), 379\u2013403 (1994)","journal-title":"Algorithmica"},{"issue":"2","key":"9151_CR19","doi-asserted-by":"crossref","first-page":"205","DOI":"10.7155\/jgaa.00106","volume":"9","author":"H. Fernau","year":"2005","unstructured":"Fernau, H.: Two-layer planarization: improving on parameterized algorithmics. J. Graph. Algorithms Appl. 9(2), 205\u2013238 (2005)","journal-title":"J. Graph. Algorithms Appl."},{"issue":"3","key":"9151_CR20","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M.R. Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebr. Discrete Methods 4(3), 312\u2013316 (1983)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"3","key":"9151_CR21","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1109\/32.221135","volume":"19","author":"E.R. Gansner","year":"1993","unstructured":"Gansner, E.R., Koutsofios, E., North, S.C., Vo, K.-P.: A technique for drawing directed graphs. IEEE Trans. Softw. Eng. 19(3), 214\u2013230 (1993)","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"2","key":"9151_CR22","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1016\/j.dam.2002.12.005","volume":"145","author":"A. Gupta","year":"2005","unstructured":"Gupta, A., Nishimura, N., Proskurowski, A., Ragde, P.: Embeddings of k-connected graphs of pathwidth k. Discrete Appl. Math. 145(2), 242\u2013265 (2005)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9151_CR23","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/j.jcss.2003.07.008","volume":"68","author":"M. Grohe","year":"2004","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. J. Comput. Syst. Sci. 68(2), 285\u2013302 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"9151_CR24","doi-asserted-by":"crossref","first-page":"927","DOI":"10.1137\/0221055","volume":"21","author":"L.S. Heath","year":"1992","unstructured":"Heath, L.S., Rosenberg, A.L.: Laying out graphs using queues. SIAM J. Comput. 21(5), 927\u2013958 (1992)","journal-title":"SIAM J. Comput."},{"key":"9151_CR25","first-page":"382","volume-title":"Proc. 39th Annual ACM Symposium on Theory of Computing (STOC \u201907)","author":"K. Kawarabayashi","year":"2007","unstructured":"Kawarabayashi, K., Reed, B.: Computing crossing number in linear time. In: Proc. 39th Annual ACM Symposium on Theory of Computing (STOC \u201907), pp. 382\u2013390. ACM Press, New York (2007)"},{"key":"9151_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"T. Lengauer","year":"1990","unstructured":"Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley, New York (1990)"},{"key":"9151_CR27","first-page":"189","volume-title":"Encyclopedia of Optimization","author":"P. Mutzel","year":"2001","unstructured":"Mutzel, P.: Optimization in leveled graphs. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, vol.\u00a04, pp. 189\u2013196. Kluwer, Dordrecht (2001)"},{"key":"9151_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/BFb0021828","volume-title":"Proc. Internat. Symp. on Graph Drawing (GD \u201995)","author":"G. Sander","year":"1996","unstructured":"Sander, G.: A fast heuristic for hierarchical Manhattan layout. In: Proc. Internat. Symp. on Graph Drawing (GD \u201995). Lecture Notes in Computer Science, vol. 1027, pp. 447\u2013458. Springer, Berlin (1996)"},{"issue":"2","key":"9151_CR29","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K. Sugiyama","year":"1981","unstructured":"Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. 11(2), 109\u2013125 (1981)","journal-title":"IEEE Trans. Syst. Man Cybern."},{"issue":"3","key":"9151_CR30","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1142\/S0218195904001433","volume":"14","author":"M. Suderman","year":"2004","unstructured":"Suderman, M.: Pathwidth and layered drawings of trees. Int. J. Comput. Geom. Appl. 14(3), 203\u2013225 (2004)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"9151_CR31","doi-asserted-by":"crossref","first-page":"149","DOI":"10.7155\/jgaa.00103","volume":"9","author":"M. Suderman","year":"2005","unstructured":"Suderman, M., Whitesides, S.: Experiments with the fixed-parameter approach for two-layer planarization. J. Graph. Algorithms Appl. 9(1), 149\u2013163 (2005)","journal-title":"J. Graph. Algorithms Appl."},{"key":"9151_CR32","first-page":"1","volume":"38","author":"N. Tomii","year":"1977","unstructured":"Tomii, N., Kambayashi, Y., Yajima, S.: On planarization algorithms of 2-level graphs. Pap. Tech. Group Electron. Comput. IECEJ 38, 1\u201312 (1977)","journal-title":"Pap. Tech. Group Electron. Comput. IECEJ"},{"issue":"7","key":"9151_CR33","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1109\/TSMC.1977.4309760","volume":"7","author":"J.N. Warfield","year":"1977","unstructured":"Warfield, J.N.: Crossing theory and hierarchy mapping. IEEE Trans. Syst. Man Cybern. 7(7), 505\u2013523 (1977)","journal-title":"IEEE Trans. Syst. Man Cybern."},{"issue":"2","key":"9151_CR34","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02460022","volume":"48","author":"M.S. Waterman","year":"1986","unstructured":"Waterman, M.S., Griggs, J.R.: Interval graphs and maps of DNA. Bull. Math. Biol. 48(2), 189\u2013195 (1986)","journal-title":"Bull. Math. Biol."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9151-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9151-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9151-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,29]],"date-time":"2020-04-29T06:18:16Z","timestamp":1588141096000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9151-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,7]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["9151"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9151-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,7]]}}}