{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:23:53Z","timestamp":1786980233613,"version":"build-2736575974"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,7,26]],"date-time":"2018-07-26T00:00:00Z","timestamp":1532563200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,7,26]],"date-time":"2018-07-26T00:00:00Z","timestamp":1532563200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00453-018-0487-5","type":"journal-article","created":{"date-parts":[[2018,7,26]],"date-time":"2018-07-26T09:23:57Z","timestamp":1532597037000},"page":"1561-1583","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Track Layouts, Layered Path Decompositions, and Leveled Planarity"],"prefix":"10.1007","volume":"81","author":[{"given":"Michael J.","family":"Bannister","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"William E.","family":"Devanny","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vida","family":"Dujmovi\u0107","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8866-3041","authenticated-orcid":false,"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,7,26]]},"reference":[{"issue":"1","key":"487_CR1","first-page":"71","volume":"9","author":"Z Abel","year":"2018","unstructured":"Abel, Z., Demaine, E.D., Demaine, M.L., Eppstein, D., Lubiw, A., Uehara, R.: Flat foldings of plane graphs with prescribed angles and edge lengths. J. Comput. Geom. 9(1), 71\u201391 (2018)","journal-title":"J. Comput. Geom."},{"issue":"4","key":"487_CR2","doi-asserted-by":"publisher","first-page":"1399","DOI":"10.1137\/090760301","volume":"24","author":"H-J Bandelt","year":"2010","unstructured":"Bandelt, H.-J., Chepoi, V., Eppstein, D.: Combinatorics and geometry of finite and infinite squaregraphs. SIAM J. Discrete Math. 24(4), 1399\u20131440 (2010). \n                    https:\/\/doi.org\/10.1137\/090760301","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"487_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.7155\/jgaa.00457","volume":"18","author":"MJ Bannister","year":"2018","unstructured":"Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. J. Graph Algorithms Appl. 18(1), 23\u201349 (2018)","journal-title":"J. Graph Algorithms Appl."},{"key":"487_CR4","doi-asserted-by":"publisher","unstructured":"Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. In: 22nd International Symposium on Graph Drawing (GD 2014), LNCS, vol. 8871, pp.\u00a0210\u2013221. Springer (2014). \n                    https:\/\/doi.org\/10.1007\/978-3-662-45803-7_18","DOI":"10.1007\/978-3-662-45803-7_18"},{"key":"487_CR5","doi-asserted-by":"publisher","unstructured":"Bannister, M.J., Eppstein, D., Simons, J.A.: Fixed parameter tractability of crossing minimization of almost-trees. In: 21st International Symposium on Graph Drawing (GD 2013), LNCS, vol. 8242, pp.\u00a0340\u2013351. Springer (2013). \n                    https:\/\/doi.org\/10.1007\/978-3-319-03841-4_30","DOI":"10.1007\/978-3-319-03841-4_30"},{"key":"487_CR6","doi-asserted-by":"publisher","unstructured":"Bastert, O., Matuszewski, C.: Layered drawings of digraphs. In: Drawing Graphs, Methods and Models, vol. 2025, pp. 87\u2013120. LNCS (2001). \n                    https:\/\/doi.org\/10.1007\/3-540-44969-8_5","DOI":"10.1007\/3-540-44969-8_5"},{"key":"487_CR7","first-page":"265","volume-title":"Layered Drawings of Digraphs, 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.: Layered Drawings of Digraphs, Graph Drawing: Algorithms for the Visualization of Graphs, pp. 265\u2013302. Prentice-Hall, Upper Saddle River (1999)"},{"key":"487_CR8","doi-asserted-by":"publisher","unstructured":"Di\u00a0Giacomo, E., Meijer, H.: Track drawings of graphs with constant queue number. In: Proceedings of 11th International Symposium on Graph Drawing (GD \u201903), LNCS, vol. 2912, pp.\u00a0214\u2013225. Springer (2004). \n                    https:\/\/doi.org\/10.1007\/978-3-540-24595-7_20","DOI":"10.1007\/978-3-540-24595-7_20"},{"key":"487_CR9","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity, Texts in Computer Science. Springer, Berlin (2013). \n                    https:\/\/doi.org\/10.1007\/978-1-4471-5559-1","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"487_CR10","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jctb.2014.07.005","volume":"110","author":"V Dujmovi\u0107","year":"2015","unstructured":"Dujmovi\u0107, V.: Graph layouts via layered separators. J. Combin. Theory Ser. B 110, 79\u201389 (2015). \n                    https:\/\/doi.org\/10.1016\/j.jctb.2014.07.005","journal-title":"J. Combin. Theory Ser. B"},{"key":"487_CR11","doi-asserted-by":"crossref","unstructured":"Dujmovi\u0107, V., Eppstein, D., Wood, D.R.: Genus, treewidth, and local crossing number. In: Proceedings of 23rd International Symposium on Graph Drawing and Network Visualization (GD \u201915), Lecture Notes in Computer Science, vol. 9411, pp.\u00a087\u201398. Springer (2015)","DOI":"10.1007\/978-3-319-27261-0_8"},{"issue":"2","key":"487_CR12","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1137\/16M1062879","volume":"31","author":"V Dujmovi\u0107","year":"2017","unstructured":"Dujmovi\u0107, V., Eppstein, D., Wood, D.R.: Structure of graphs with locally restricted crossings. SIAM J. Disc. Math. 31(2), 805\u2013824 (2017). \n                    https:\/\/doi.org\/10.1137\/16M1062879","journal-title":"SIAM J. Disc. Math."},{"issue":"2","key":"487_CR13","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s00453-007-9151-1","volume":"52","author":"V Dujmovi\u0107","year":"2008","unstructured":"Dujmovi\u0107, V., Fellows, M.R., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Whitesides, S., Wood, D.R.: On the parameterized complexity of layered graph drawing. Algorithmica 52(2), 267\u2013292 (2008). \n                    https:\/\/doi.org\/10.1007\/s00453-007-9151-1","journal-title":"Algorithmica"},{"key":"487_CR14","doi-asserted-by":"publisher","first-page":"89","DOI":"10.7155\/jgaa.00454","volume":"22","author":"V Dujmovi\u0107","year":"2018","unstructured":"Dujmovi\u0107, V., Frati, F.: Stacks and queue layouts via layered separators. J. Graph Algorithms Appl. 22, 89\u201399 (2018). \n                    https:\/\/doi.org\/10.7155\/jgaa.00454","journal-title":"J. Graph Algorithms Appl."},{"key":"487_CR15","doi-asserted-by":"publisher","unstructured":"Dujmovi\u0107, V., Joret, G., Morin, P., Norin, S., Wood, D.R.: Orthogonal tree decompositions of graphs. SIAM J. Discrete Math. 32(2), 839\u2013863 (2018). \n                    arXiv: 1701.05639\n                    \n                  . \n                    https:\/\/doi.org\/10.1137\/17M1112637","DOI":"10.1137\/17M1112637"},{"issue":"3","key":"487_CR16","doi-asserted-by":"publisher","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). \n                    https:\/\/doi.org\/10.1137\/S0097539702416141","journal-title":"SIAM J. Comput."},{"key":"487_CR17","doi-asserted-by":"publisher","unstructured":"Dujmovi\u0107, V., Morin, P., Wood, D.R.: Layered separators for queue layouts, 3D graph drawing and nonrepetitive coloring. In: Proceedings of 54th Symposium on Foundations of Computer Science (FOCS 2013), pp.\u00a0280\u2013289. IEEE Computer Society (2013). \n                    https:\/\/doi.org\/10.1109\/FOCS.2013.38","DOI":"10.1109\/FOCS.2013.38"},{"key":"487_CR18","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.jctb.2017.05.006","volume":"127","author":"V Dujmovi\u0107","year":"2017","unstructured":"Dujmovi\u0107, V., Morin, P., Wood, D.R.: Layered separators in minor-closed graph classes with applications. J. Combin. Theory Ser. B 127, 111\u2013147 (2017). \n                    https:\/\/doi.org\/10.1016\/j.jctb.2017.05.006","journal-title":"J. Combin. Theory Ser. B"},{"key":"487_CR19","unstructured":"Dujmovi\u0107, V., P\u00f3r, A., Wood, D.R.: Track layouts of graphs. Discrete Math. Theor. Comput. Sci. 6(2), 497\u2013521 (2004). \n                    http:\/\/dmtcs.episciences.org\/315"},{"key":"487_CR20","doi-asserted-by":"publisher","unstructured":"Dujmovi\u0107, V., Sidiropoulos, A., Wood, D.R.: Layouts of expander graphs. Chic. J. Theor. Comput. Sci. 2016(1) (2016). \n                    https:\/\/doi.org\/10.4086\/cjtcs.2016.001","DOI":"10.4086\/cjtcs.2016.001"},{"key":"487_CR21","doi-asserted-by":"publisher","unstructured":"Dujmovi\u0107, V., Wood, D.R.: Three-dimensional grid drawings with sub-quadratic volume. In: J\u00e1nos, P. (ed.) Towards a Theory of Geometric Graphs, Contemporary Mathematics, vol. 342, pp.\u00a055\u201366. American Mathematical Society, Providence (2004). \n                    https:\/\/doi.org\/10.1090\/conm\/342\/06130","DOI":"10.1090\/conm\/342\/06130"},{"key":"487_CR22","unstructured":"Dujmovi\u0107, V., Wood, D.R.: Stacks, queues and tracks: layouts of graph subdivisions. Discrete Math. Theor. Comput. Sci. 7(1), 155\u2013201 (2005). \n                    http:\/\/dmtcs.episciences.org\/346"},{"issue":"4","key":"487_CR23","doi-asserted-by":"publisher","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). \n                    https:\/\/doi.org\/10.1007\/BF01187020","journal-title":"Algorithmica"},{"issue":"4","key":"487_CR24","doi-asserted-by":"publisher","first-page":"363","DOI":"10.7155\/jgaa.00075","volume":"7","author":"S Felsner","year":"2003","unstructured":"Felsner, S., Liotta, G., Wismath, S.K.: Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Algorithms Appl. 7(4), 363\u2013398 (2003). \n                    https:\/\/doi.org\/10.7155\/jgaa.00075","journal-title":"J. Graph Algorithms Appl."},{"key":"487_CR25","unstructured":"Halin, R.: Studies on minimally $$n$$-connected graphs. In: Combinatorial Mathematics and Its Applications (Proc. Conf., Oxford, 1969), pp.\u00a0129\u2013136. Academic Press (1971)"},{"issue":"1\u20132","key":"487_CR26","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01917434","volume":"8","author":"R Halin","year":"1976","unstructured":"Halin, R.: $$S$$-functions for graphs. J. Geom. 8(1\u20132), 171\u2013186 (1976). \n                    https:\/\/doi.org\/10.1007\/BF01917434","journal-title":"J. Geom."},{"key":"487_CR27","first-page":"203","volume":"1","author":"F Harary","year":"1972","unstructured":"Harary, F., Schwenk, A.: A new crossing number for bipartite graphs. Util. Math. 1, 203\u2013209 (1972)","journal-title":"Util. Math."},{"issue":"4","key":"487_CR28","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1002\/jgt.22030","volume":"84","author":"DJ Harvey","year":"2017","unstructured":"Harvey, D.J., Wood, D.R.: Parameters tied to treewidth. J. Graph Theory 84(4), 364\u2013385 (2017). \n                    https:\/\/doi.org\/10.1002\/jgt.22030","journal-title":"J. Graph Theory"},{"key":"487_CR29","doi-asserted-by":"publisher","unstructured":"Healy, P., Nikolov, N.S.: How to layer a directed acyclic graph. In: 9th International Symposium on Graph Drawing (GD 2001), LNCS, vol. 2265, pp.\u00a016\u201330. Springer (2002). \n                    https:\/\/doi.org\/10.1007\/3-540-45848-4_2","DOI":"10.1007\/3-540-45848-4_2"},{"key":"487_CR30","first-page":"409","volume-title":"Hierarchical Drawing Algorithms, Handbook on Graph Drawing and Visualization","author":"P Healy","year":"2013","unstructured":"Healy, P., Nikolov, N.S.: Hierarchical Drawing Algorithms, Handbook on Graph Drawing and Visualization, pp. 409\u2013453. CRC Press, Boca Raton (2013)"},{"issue":"5","key":"487_CR31","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1137\/0221055","volume":"21","author":"LS Heath","year":"1992","unstructured":"Heath, L.S., Rosenberg, A.L.: Laying out graphs using queues. SIAM J. Comput. 21(5), 927\u2013958 (1992). \n                    https:\/\/doi.org\/10.1137\/0221055","journal-title":"SIAM J. Comput."},{"key":"487_CR32","doi-asserted-by":"publisher","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Sparsity (Graphs, Structures, and Algorithms), Algorithms and Combinatorics, vol.\u00a028. Springer, Berlin (2012). \n                    https:\/\/doi.org\/10.1007\/978-3-642-27875-4","DOI":"10.1007\/978-3-642-27875-4"},{"issue":"1","key":"487_CR33","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.: Graph minors, I: excluding a forest. J. Combin. Theory Ser. B 35(1), 39\u201361 (1983). \n                    https:\/\/doi.org\/10.1016\/0095-8956(83)90079-5","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"487_CR34","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986). \n                    https:\/\/doi.org\/10.1016\/0196-6774(86)90023-4","journal-title":"J. Algorithms"},{"key":"487_CR35","doi-asserted-by":"publisher","unstructured":"Scheffler, P.: Optimal embedding of a tree into an interval graph in linear time. In: 4th Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, Annals of Discrete Mathematics, vol.\u00a051, pp.\u00a0287\u2013291. North-Holland (1992). \n                    https:\/\/doi.org\/10.1016\/S0167-5060(08)70644-7","DOI":"10.1016\/S0167-5060(08)70644-7"},{"key":"487_CR36","unstructured":"Shahrokhi, F.: New representation results for planar graphs. In: 29th European Workshop on Computational Geometry (EuroCG 2013), pp.\u00a0177\u2013180 (2013). \n                    arXiv: 1502.06175"},{"issue":"2","key":"487_CR37","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"SMC\u201311","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. SMC\u201311(2), 109\u2013125 (1981). \n                    https:\/\/doi.org\/10.1109\/TSMC.1981.4308636","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"487_CR38","unstructured":"Wikipedia: Winding Number (2016). \n                    https:\/\/en.wikipedia.org\/wiki\/Winding_number\n                    \n                  . Accessed 24 July 2018"},{"key":"487_CR39","unstructured":"Wood, D.R.: Clique minors in Cartesian products of graphs. N. Y. J. Math. 17, 627\u2013682 (2011). \n                    http:\/\/nyjm.albany.edu\/j\/2011\/17-28.html"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0487-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0487-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0487-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T02:32:42Z","timestamp":1589682762000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0487-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,26]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["487"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0487-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,26]]},"assertion":[{"value":"7 May 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}