{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:36Z","timestamp":1781078256137,"version":"3.54.1"},"reference-count":115,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T00:00:00Z","timestamp":1596672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Polish National Science Center"},{"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\/501100002790","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Wallonia-Brussels Federation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>\n            We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et\u00a0al. [66] from 1992. The key to the proof is a new structural tool called\n            <jats:italic>layered partitions<\/jats:italic>\n            , and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number.\n          <\/jats:p>\n          <jats:p>Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et\u00a0al. [31] that graphs in a proper minor-closed class have low treewidth colourings.<\/jats:p>","DOI":"10.1145\/3385731","type":"journal-article","created":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T12:37:50Z","timestamp":1594125470000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":66,"title":["Planar Graphs Have Bounded Queue-Number"],"prefix":"10.1145","volume":"67","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[{"name":"University of Ottawa, Ottawa, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles, Brussels, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Micek","sequence":"additional","affiliation":[{"name":"Jagiellonian University, Krak\u00f3w, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Torsten","family":"Ueckerdt","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[{"name":"Monash University, Melbourne, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,8,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Ziegler","author":"Aigner Martin","year":"2010","unstructured":"Martin Aigner and G\u00fcnter M . Ziegler . 2010 . Proofs from the Book (4th ed.). Springer . Martin Aigner and G\u00fcnter M. Ziegler. 2010. Proofs from the Book (4th ed.). Springer."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04414-5_15"},{"key":"e_1_2_1_3_1","volume-title":"Queue layouts of planar 3-trees. Algorithmica","author":"Alam Jawaherul Md.","year":"2020","unstructured":"Jawaherul Md. Alam , Michael A. Bekos , Martin Gronemann , Michael Kaufmann , and Sergey Pupyrev . 2020. Queue layouts of planar 3-trees. Algorithmica ( 2020 ). DOI:https:\/\/doi.org\/10.1007\/s00453-020-00697-4 Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, Michael Kaufmann, and Sergey Pupyrev. 2020. Queue layouts of planar 3-trees. Algorithmica (2020). DOI:https:\/\/doi.org\/10.1007\/s00453-020-00697-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(01)00455-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286320.1286324"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02762708"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90026-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73486-8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0487-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M125340X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402014"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0854"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.27"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90077-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00276-8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.10.010"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 16th ACM Symposium. on Theory of Computing (STOC\u201984)","author":"Jonathan","unstructured":"Jonathan F. Buss and Peter Shor. 1984. On the pagenumber of planar graphs . In Proceedings of the 16th ACM Symposium. on Theory of Computing (STOC\u201984) . ACM, 98\u2013100. DOI:https:\/\/doi.org\/10.1145\/800057.808670 Jonathan F. Buss and Peter Shor. 1984. On the pagenumber of planar graphs. In Proceedings of the 16th ACM Symposium. on Theory of Computing (STOC\u201984). ACM, 98\u2013100. DOI:https:\/\/doi.org\/10.1145\/800057.808670"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.12.002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-008-0795-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1178"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1272412.1272414"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506148"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02522826"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077468"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1106-1"},{"key":"e_1_2_1_29_1","volume-title":"Demaine and MohammadTaghi Hajiaghayi","author":"Erik","year":"2004","unstructured":"Erik D. Demaine and MohammadTaghi Hajiaghayi . 2004 . Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904). SIAM , 840\u2013849. http:\/\/dl.acm.org\/citation.cfm?id=982792.982919. Erik D. Demaine and MohammadTaghi Hajiaghayi. 2004. Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904). SIAM, 840\u2013849. http:\/\/dl.acm.org\/citation.cfm?id=982792.982919."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.09.001"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/130908051"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24595-7_20"},{"key":"e_1_2_1_34_1","volume-title":"Graph Theory","author":"Diestel Reinhard","year":"2066","unstructured":"Reinhard Diestel . 2018. Graph Theory ( 5 th ed.). Graduate Texts in Mathematics, Vol. 173 . Springer . MR:\u00a0382 2066 . Reinhard Diestel. 2018. Graph Theory (5th ed.). Graduate Texts in Mathematics, Vol. 173. Springer. MR:\u00a03822066.","edition":"5"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1056106.1704950"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190200412"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00337-I"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050001"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1962"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.136"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.07.005"},{"key":"e_1_2_1_42_1","volume-title":"Wood","author":"Dujmovi\u0107 Vida","year":"2018","unstructured":"Vida Dujmovi\u0107 , David Eppstein , Gwena\u00ebl Joret , Pat Morin , and David R . Wood . 2018 . Minor-closed graph classes with bounded layered pathwidth. arXiv:\u00a01810.08314. Vida Dujmovi\u0107, David Eppstein, Gwena\u00ebl Joret, Pat Morin, and David R. Wood. 2018. Minor-closed graph classes with bounded layered pathwidth. arXiv:\u00a01810.08314."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1062879"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Vida Dujmovi\u0107 Louis Esperet Gwena\u00ebl Joret Cyril Gavoille Piotr Micek and Pat Morin. 2020. Adjacency labelling for planar graphs (and beyond). (2020). arXiv:\u00a02003.04280.  Vida Dujmovi\u0107 Louis Esperet Gwena\u00ebl Joret Cyril Gavoille Piotr Micek and Pat Morin. 2020. Adjacency labelling for planar graphs (and beyond). (2020). arXiv:\u00a02003.04280.","DOI":"10.1109\/FOCS46700.2020.00060"},{"key":"e_1_2_1_45_1","volume-title":"Wood","author":"Dujmovi\u0107 Vida","year":"2020","unstructured":"Vida Dujmovi\u0107 , Louis Esperet , Gwena\u00ebl Joret , Bartosz Walczak , and David R . Wood . 2020 . Planar graphs have bounded nonrepetitive chromatic number. Advances in Combinatorics 5 (2020). DOI:https:\/\/doi.org\/10.19086\/aic.12100 Vida Dujmovi\u0107, Louis Esperet, Gwena\u00ebl Joret, Bartosz Walczak, and David R. Wood. 2020. Planar graphs have bounded nonrepetitive chromatic number. Advances in Combinatorics 5 (2020). DOI:https:\/\/doi.org\/10.19086\/aic.12100"},{"key":"e_1_2_1_46_1","volume-title":"Wood","author":"Dujmovi\u0107 Vida","year":"2020","unstructured":"Vida Dujmovi\u0107 , Louis Esperet , Pat Morin , Bartosz Walczak , and David R . Wood . 2020 . Clustered 3-colouring graphs of bounded degree. (2020). arXiv:\u00a02002.11721. Vida Dujmovi\u0107, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood. 2020. Clustered 3-colouring graphs of bounded degree. (2020). arXiv:\u00a02002.11721."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00454"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416141"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.05.006"},{"key":"e_1_2_1_50_1","volume-title":"Wood","author":"Dujmovi\u0107 Vida","year":"2019","unstructured":"Vida Dujmovi\u0107 , Pat Morin , and David R . Wood . 2019 . Queue layouts of graphs with bounded degree and bounded genus. (2019). arXiv:\u00a01901.05594. Vida Dujmovi\u0107, Pat Morin, and David R. Wood. 2019. Queue layouts of graphs with bounded degree and bounded genus. (2019). arXiv:\u00a01901.05594."},{"key":"e_1_2_1_51_1","first-page":"497","article-title":"Track layouts of graphs","volume":"6","author":"Dujmovi\u0107 Vida","year":"2004","unstructured":"Vida Dujmovi\u0107 , Attila P\u00f3r , and David R. Wood . 2004 . Track layouts of graphs . Discrete Math. Theor. Comput. Sci. 6 , 2 (2004), 497 \u2013 522 . http:\/\/dmtcs.episciences.org\/315 MR:\u00a02180055. Vida Dujmovi\u0107, Attila P\u00f3r, and David R. Wood. 2004. Track layouts of graphs. Discrete Math. Theor. Comput. Sci. 6, 2 (2004), 497\u2013522. http:\/\/dmtcs.episciences.org\/315 MR:\u00a02180055.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"e_1_2_1_52_1","first-page":"339","article-title":"On linear layouts of graphs","volume":"6","author":"Dujmovi\u0107 Vida","year":"2004","unstructured":"Vida Dujmovi\u0107 and David R. Wood . 2004 . On linear layouts of graphs . Discrete Math. Theor. Comput. Sci. 6 , 2 (2004), 339 \u2013 358 . http:\/\/dmtcs.episciences.org\/317 MR:\u00a02081479. Vida Dujmovi\u0107 and David R. Wood. 2004. On linear layouts of graphs. Discrete Math. Theor. Comput. Sci. 6, 2 (2004), 339\u2013358. http:\/\/dmtcs.episciences.org\/317 MR:\u00a02081479.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"e_1_2_1_53_1","first-page":"55","article-title":"Three-dimensional grid drawings with sub-quadratic volume. In Towards a Theory of Geometric Graphs, J\u00e1nos Pach (Ed.). Contemporary Mathematics, vol. 342","author":"Dujmovi\u0107 Vida","year":"2004","unstructured":"Vida Dujmovi\u0107 and David R. Wood . 2004 . Three-dimensional grid drawings with sub-quadratic volume. In Towards a Theory of Geometric Graphs, J\u00e1nos Pach (Ed.). Contemporary Mathematics, vol. 342 . Amer. Math. Soc. , 55 \u2013 66 . MR:\u00a02065252. Vida Dujmovi\u0107 and David R. Wood. 2004. Three-dimensional grid drawings with sub-quadratic volume. In Towards a Theory of Geometric Graphs, J\u00e1nos Pach (Ed.). Contemporary Mathematics, vol. 342. Amer. Math. Soc., 55\u201366. MR:\u00a02065252.","journal-title":"Amer. Math. Soc."},{"key":"e_1_2_1_54_1","first-page":"155","article-title":"Stacks, queues and tracks: Layouts of graph subdivisions","volume":"7","author":"Dujmovi\u0107 Vida","year":"2005","unstructured":"Vida Dujmovi\u0107 and David R. Wood . 2005 . Stacks, queues and tracks: Layouts of graph subdivisions . Discrete Math. Theor. Comput. Sci. 7 (2005), 155 \u2013 202 . http:\/\/dmtcs.episciences.org\/346 MR:\u00a02164064. Vida Dujmovi\u0107 and David R. Wood. 2005. Stacks, queues and tracks: Layouts of graph subdivisions. Discrete Math. Theor. Comput. Sci. 7 (2005), 155\u2013202. http:\/\/dmtcs.episciences.org\/346 MR:\u00a02164064.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-006-9028-y"},{"key":"e_1_2_1_56_1","volume-title":"Wood","author":"Dvo\u0159\u00e1k Zden\u011bk","year":"2020","unstructured":"Zden\u011bk Dvo\u0159\u00e1k , Tony Huynh , Gwena\u00ebl Joret , Chun-Hung Liu , and David R . Wood . 2020 . Notes on graph product structure theory. (2020). arXiv:\u00a02001.08860. Zden\u011bk Dvo\u0159\u00e1k, Tony Huynh, Gwena\u00ebl Joret, Chun-Hung Liu, and David R. Wood. 2020. Notes on graph product structure theory. (2020). arXiv:\u00a02001.08860."},{"key":"e_1_2_1_57_1","unstructured":"Zden\u011bk Dvo\u0159\u00e1k and Robin Thomas. 2014. List-coloring apex-minor-free graphs. arXiv:\u00a01401.1399.  Zden\u011bk Dvo\u0159\u00e1k and Robin Thomas. 2014. List-coloring apex-minor-free graphs. arXiv:\u00a01401.1399."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, 1038\u20131046","author":"Erickson Jeff","year":"2005","unstructured":"Jeff Erickson and Kim Whittlesey . 2005 . Greedy optimal homotopy and homology generators . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, 1038\u20131046 . Jeff Erickson and Kim Whittlesey. 2005. Greedy optimal homotopy and homology generators. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, 1038\u20131046."},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the 9th International Symposium on Graph Drawing (GD\u201901)","volume":"2265","author":"Felsner Stefan","unstructured":"Stefan Felsner , Giussepe Liotta , and Stephen K. Wismath . 2002. Straight-line drawings on restricted integer grids in two and three dimensions . In Proceedings of the 9th International Symposium on Graph Drawing (GD\u201901) (Computer Science), Petra Mutzel, Michael J\u00fcnger, and Sebastian Leipert (Eds.) , vol. 2265 . Springer, 328\u2013342. Stefan Felsner, Giussepe Liotta, and Stephen K. Wismath. 2002. Straight-line drawings on restricted integer grids in two and three dimensions. In Proceedings of the 9th International Symposium on Graph Drawing (GD\u201901)(Computer Science), Petra Mutzel, Michael J\u00fcnger, and Sebastian Leipert (Eds.), vol. 2265. Springer, 328\u2013342."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.124"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990459"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000412"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22030"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.04.045"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405031"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193252380"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221055"},{"key":"e_1_2_1_69_1","volume-title":"Rosenberg","author":"Heath Lenwood S.","year":"2011","unstructured":"Lenwood S. Heath and Arnold L . Rosenberg . 2011 . Graph Layout using Queues . (2011). https:\/\/www.researchgate.net\/publication\/220616637_Laying_Out_Graphs_Using_Queues Lenwood S. Heath and Arnold L. Rosenberg. 2011. Graph Layout using Queues. (2011). https:\/\/www.researchgate.net\/publication\/220616637_Laying_Out_Graphs_Using_Queues"},{"key":"e_1_2_1_70_1","first-page":"332","article-title":"Map colour theorem","volume":"24","author":"Heawood Percy J.","year":"1890","unstructured":"Percy J. Heawood . 1890 . Map colour theorem . Quart. J. Pure Appl. Math. 24 (1890), 332 \u2013 338 . DOI:https:\/\/doi.org\/10.1112\/plms\/s2-51.3.161 Percy J. Heawood. 1890. Map colour theorem. Quart. J. Pure Appl. Math. 24 (1890), 332\u2013338. DOI:https:\/\/doi.org\/10.1112\/plms\/s2-51.3.161","journal-title":"Quart. J. Pure Appl. Math."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.06.019"},{"key":"e_1_2_1_72_1","volume-title":"Wood","author":"van den Heuvel Jan","year":"2017","unstructured":"Jan van den Heuvel and David R . Wood . 2017 . Improper colourings inspired by Hadwiger\u2019s Conjecture . (2017). arXiv:\u00a01704.06536. Jan van den Heuvel and David R. Wood. 2017. Improper colourings inspired by Hadwiger\u2019s Conjecture. (2017). arXiv:\u00a01704.06536."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12127"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62244"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405049"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:ORDE.0000026489.93166.cb"},{"key":"e_1_2_1_77_1","volume-title":"Graph Drawing and Network Visualization (Lecture Notes in Computer Science)","author":"Knauer Kolja","unstructured":"Kolja Knauer , Piotr Micek , and Torsten Ueckerdt . 2018. The queue-number of posets of bounded width or height . In Graph Drawing and Network Visualization (Lecture Notes in Computer Science) , vol. 11282 . Springer , 200\u2013212. Kolja Knauer, Piotr Micek, and Torsten Ueckerdt. 2018. The queue-number of posets of bounded width or height. In Graph Drawing and Network Visualization (Lecture Notes in Computer Science), vol. 11282. Springer, 200\u2013212."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2017.06.002"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.2000.0428"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.5555\/2747009.2747067"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90091-W"},{"key":"e_1_2_1_82_1","unstructured":"Jan Kratochv\u00edl and Michal Vaner. 2012. A note on planar partial 3-trees. (2012). arXiv:\u00a01210.8113.  Jan Kratochv\u00edl and Michal Vaner. 2012. A note on planar partial 3-trees. (2012). arXiv:\u00a01210.8113."},{"key":"e_1_2_1_83_1","volume-title":"Wood","author":"Liu Chun-Hung","year":"2019","unstructured":"Chun-Hung Liu and David R . Wood . 2019 . Clustered graph coloring and layered treewidth. arXiv:\u00a01905.08969. Chun-Hung Liu and David R. Wood. 2019. Clustered graph coloring and layered treewidth. arXiv:\u00a01905.08969."},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1028"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019529248X"},{"key":"e_1_2_1_86_1","volume-title":"Graphs on Surfaces","author":"Mohar Bojan","year":"1844","unstructured":"Bojan Mohar and Carsten Thomassen . 2001. Graphs on Surfaces . Johns Hopkins University Press . MR:\u00a0 1844 449. Bojan Mohar and Carsten Thomassen. 2001. Graphs on Surfaces. Johns Hopkins University Press. MR:\u00a01844449."},{"key":"e_1_2_1_87_1","unstructured":"Pat Morin. 2020. A fast algorithm for the product structure of planar graphs. (2020). arXiv:\u00a02004.02530.  Pat Morin. 2020. A fast algorithm for the product structure of planar graphs. (2020). arXiv:\u00a02004.02530."},{"key":"e_1_2_1_88_1","volume-title":"Algorithms and Combinatorics","author":"Ne\u0161et\u0159il Jaroslav","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez . 2012. Sparsity. Algorithms and Combinatorics , vol. 28 . Springer . DOI:https:\/\/doi.org\/10.1007\/978-3-642-27875-4 MR:\u00a02920058. Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity. Algorithms and Combinatorics, vol. 28. Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-642-27875-4 MR:\u00a02920058."},{"key":"e_1_2_1_89_1","volume-title":"Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing (Congr. Numer.), Frederick Hoffman, Roy B. Levow, and Robert S. D. Thomas (Eds.)","author":"Ollmann L. Taylor","year":"1973","unstructured":"L. Taylor Ollmann . 1973 . On the book thicknesses of various graphs . In Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing (Congr. Numer.), Frederick Hoffman, Roy B. Levow, and Robert S. D. Thomas (Eds.) , vol. VIII . Utilitas Math., 459. L. Taylor Ollmann. 1973. On the book thicknesses of various graphs. In Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing (Congr. Numer.), Frederick Hoffman, Roy B. Levow, and Robert S. D. Thomas (Eds.), vol. VIII. Utilitas Math., 459."},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-018-3733-1"},{"key":"e_1_2_1_91_1","volume-title":"Advances in Discrete and Computational Geometry","author":"Pach J\u00e1nos","unstructured":"J\u00e1nos Pach , Torsten Thiele , and G\u00e9za T\u00f3th . 1999. Three-dimensional grid drawings of graphs . In Advances in Discrete and Computational Geometry , Bernard Chazelle , Jacob E. Goodman, and Richard Pollack (Eds.). Contemporary Mathematics, vol. 223 . Amer. Math. Soc., 251\u2013255. MR :\u00a01661387. J\u00e1nos Pach, Torsten Thiele, and G\u00e9za T\u00f3th. 1999. Three-dimensional grid drawings of graphs. In Advances in Discrete and Computational Geometry, Bernard Chazelle, Jacob E. Goodman, and Richard Pollack (Eds.). Contemporary Mathematics, vol. 223. Amer. Math. Soc., 251\u2013255. MR:\u00a01661387."},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2891-4"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.91"},{"key":"e_1_2_1_95_1","unstructured":"Sergey Pupyrev. 2019. Improved bounds for track numbers of planar graphs. (2019). arXiv:\u00a01910.14153.  Sergey Pupyrev. 2019. Improved bounds for track numbers of planar graphs. (2019). arXiv:\u00a01910.14153."},{"key":"e_1_2_1_96_1","volume-title":"Surveys in Combinatorics.","author":"Reed Bruce A.","unstructured":"Bruce A. Reed . 1997. Tree width and tangles: A new connectivity measure and some applications . In Surveys in Combinatorics. London Math . Soc. Lecture Note Ser., vol. 241 . Cambridge University Press , 87\u2013162. DOI:https:\/\/doi.org\/10.1017\/CBO9780511662119.006 MR:\u00a01477746. Bruce A. Reed. 1997. Tree width and tangles: A new connectivity measure and some applications. In Surveys in Combinatorics. London Math. Soc. Lecture Note Ser., vol. 241. Cambridge University Press, 87\u2013162. DOI:https:\/\/doi.org\/10.1017\/CBO9780511662119.006 MR:\u00a01477746."},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1835"},{"key":"e_1_2_1_98_1","volume-title":"Proceedings of the 1st Annual International Conference on Computing and Combinatorics (COCOON\u201995)","volume":"959","author":"Rengarajan S.","unstructured":"S. Rengarajan and C. E. Veni Madhavan . 1995. Stack and queue number of 2-trees . In Proceedings of the 1st Annual International Conference on Computing and Combinatorics (COCOON\u201995) (Lecture Notes in Computer Science), Ding-Zhu Du and Ming Li (Eds.) , vol. 959 . Springer, 203\u2013212. DOI:https:\/\/doi.org\/10.1007\/BFb0030834 S. Rengarajan and C. E. Veni Madhavan. 1995. Stack and queue number of 2-trees. In Proceedings of the 1st Annual International Conference on Computing and Combinatorics (COCOON\u201995) (Lecture Notes in Computer Science), Ding-Zhu Du and Ming Li (Eds.), vol. 959. Springer, 203\u2013212. DOI:https:\/\/doi.org\/10.1007\/BFb0030834"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00045-X"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.002"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22363"},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028825"},{"key":"e_1_2_1_105_1","volume-title":"Proceedings of the 29th European Workshop on Computational Geometry (EuroCG","author":"Shahrokhi Farhad","year":"2013","unstructured":"Farhad Shahrokhi . 2013 . New representation results for planar graphs . In Proceedings of the 29th European Workshop on Computational Geometry (EuroCG 2013). 177\u2013180. arXiv:\u00a01502.06175. Farhad Shahrokhi. 2013. New representation results for planar graphs. In Proceedings of the 29th European Workshop on Computational Geometry (EuroCG 2013). 177\u2013180. arXiv:\u00a01502.06175."},{"key":"e_1_2_1_106_1","unstructured":"Jiun-Jie Wang. 2017. Layouts for plane graphs on constant number of tracks. (2017). arXiv:\u00a01708.02114.  Jiun-Jie Wang. 2017. Layouts for plane graphs on constant number of tracks. (2017). arXiv:\u00a01708.02114."},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.37236\/6429"},{"key":"e_1_2_1_108_1","first-page":"255","article-title":"Queue layouts of graph products and powers","volume":"7","author":"Wood David R.","year":"2005","unstructured":"David R. Wood . 2005 . Queue layouts of graph products and powers . Discrete Math. Theor. Comput. Sci. 7 , 1 (2005), 255 \u2013 268 . http:\/\/dmtcs.episciences.org\/352 MR:\u00a02183176. David R. Wood. 2005. Queue layouts of graph products and powers. Discrete Math. Theor. Comput. Sci. 7, 1 (2005), 255\u2013268. http:\/\/dmtcs.episciences.org\/352 MR:\u00a02183176.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"e_1_2_1_109_1","first-page":"27","article-title":"Bounded-degree graphs have arbitrarily large queue-number","volume":"10","author":"Wood David R.","year":"2008","unstructured":"David R. Wood . 2008 . Bounded-degree graphs have arbitrarily large queue-number . Discrete Math. Theor. Comput. Sci. 10 , 1 (2008), 27 \u2013 34 . http:\/\/dmtcs.episciences.org\/434 MR:\u00a02369152. David R. Wood. 2008. Bounded-degree graphs have arbitrarily large queue-number. Discrete Math. Theor. Comput. Sci. 10, 1 (2008), 27\u201334. http:\/\/dmtcs.episciences.org\/434 MR:\u00a02369152.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"e_1_2_1_110_1","unstructured":"David R. Wood. 2008. The structure of Cartesian products. (2008). https:\/\/www.birs.ca\/workshops\/2008\/08w5079\/report08w5079.pdf  David R. Wood. 2008. The structure of Cartesian products. (2008). https:\/\/www.birs.ca\/workshops\/2008\/08w5079\/report08w5079.pdf"},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2008.11.010"},{"key":"e_1_2_1_112_1","first-page":"627","article-title":"Clique minors in Cartesian products of graphs","volume":"17","author":"Wood David R.","year":"2011","unstructured":"David R. Wood . 2011 . Clique minors in Cartesian products of graphs . New York J. Math. 17 (2011), 627 \u2013 682 . http:\/\/nyjm.albany.edu\/j\/2011\/17-28.html David R. Wood. 2011. Clique minors in Cartesian products of graphs. New York J. Math. 17 (2011), 627\u2013682. http:\/\/nyjm.albany.edu\/j\/2011\/17-28.html","journal-title":"New York J. Math."},{"key":"e_1_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21677"},{"key":"e_1_2_1_114_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2010.05.007"},{"key":"e_1_2_1_115_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90032-9"},{"key":"e_1_2_1_116_1","volume-title":"Wood","author":"Dujmovi\u0107 Vida","year":"2019","unstructured":"Vida Dujmovi\u0107 , Pat Morin , and David R . Wood . 2019 . Graph product structure for non-minor-closed classes. arXiv: 1907.05168. Vida Dujmovi\u0107, Pat Morin, and David R. Wood. 2019. Graph product structure for non-minor-closed classes. arXiv: 1907.05168."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385731","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3385731","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:50Z","timestamp":1750199570000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385731"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,6]]},"references-count":115,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3385731"],"URL":"https:\/\/doi.org\/10.1145\/3385731","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,6]]},"assertion":[{"value":"2019-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}