{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:38:15Z","timestamp":1787341095648,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Ka812\/17-1"],"award-info":[{"award-number":["Ka812\/17-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","award":["57419183"],"award-info":[{"award-number":["57419183"]}],"id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell'Istruzione, dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["20174LF3T8"],"award-info":[{"award-number":["20174LF3T8"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>A queue layout of a graph consists of a linear order of its vertices and a partition of its edges into queues, so that no two independent edges of the same queue are nested. The queue number of a graph is the minimum number of queues required by any of its queue layouts. A long-standing conjecture by Heath, Leighton and Rosenberg [ SIAM J. Discrete Math., 5 (1992), pp. 398--412] states that the queue number of planar graphs is bounded. This conjecture has been partially settled in the positive for several subfamilies of planar graphs (most of which have bounded treewidth). In this paper, we make a further important step towards settling this conjecture. We prove that planar graphs of bounded degree (which may have unbounded treewidth) have bounded queue number. A notable implication of this result is that every planar graph of bounded degree admits a three-dimensional straight-line grid drawing in linear volume. Further implications are that every planar graph of bounded degree has bounded track number, and that every $k$-planar graph (i.e., every graph that can be drawn in the plane with at most $k$ crossings per edge) of bounded degree has bounded queue number.<\/jats:p>","DOI":"10.1137\/19m125340x","type":"journal-article","created":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T12:14:50Z","timestamp":1570104890000},"page":"1487-1502","source":"Crossref","is-referenced-by-count":11,"title":["Planar Graphs of Bounded Degree Have Bounded Queue Number"],"prefix":"10.1137","volume":"48","author":[{"given":"Michael A.","family":"Bekos","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Henry","family":"F\u00f6rster","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Gronemann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tamara","family":"Mchedlidze","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0543-8912","authenticated-orcid":true,"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chrysanthi","family":"Raftopoulou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Torsten","family":"Ueckerdt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,10,3]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04414-5_15"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0487-5"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"M. A. Bekos, H. F\u00f6rster, M. Gronemann, T. Mchedlidze, F. Montecchiani, C. N. Raftopoulou, and T. Ueckerdt,\n                      Planar Graphs of Bounded Degree have Constant Queue Number\n                      , preprint,http:\/\/arxiv.org\/abs\/1811.00816, 2018.","DOI":"10.1145\/3313276.3316324"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0024"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90077-3"},{"key":"atypb6","unstructured":"E. D. Demaine, J. S. B. Mitchell, and J. O'Rourke,\n                      The Open Problems Project (Problem 52: Queue-Number of Planar Graphs)\n                      ,http:\/\/cs.smith.edu\/~jorourke\/TOPP\/P52.html, 2003 (accessed online March 19, 2019)."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/130908051"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.11.003"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 4th ed., Grad. Texts in Math. 173, Springer, Berlin, 2012.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.07.005"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00454"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"V. Dujmovic, G. Joret, P. Micek, P. Morin, T. Ueckerdt, and D. R. Wood,\n                      Planar Graphs have Bounded Queue-number\n                      , preprint,http:\/\/arxiv.org\/abs\/1904.04791, 2019.","DOI":"10.1109\/FOCS.2019.00056"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"V. Dujmovic, G. Joret, P. Micek, P. Morin, T. Ueckerdt, and D. R. Wood,\n                      Planar graphs have bounded queue-number\n                      , in FOCS, IEEE Computer Society, 2019, accepted.","DOI":"10.1109\/FOCS.2019.00056"},{"key":"atypb14","first-page":"42","author":"Dujmovic V.","year":"2002","journal-title":"Berlin"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416141"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.05.006"},{"key":"atypb17","unstructured":"V. Dujmovic, P. Morin, and D. R. Wood,\n                      Queue Layouts of Graphs with Bounded Degree and Bounded Genus\n                      , preprint,http:\/\/arxiv.org\/abs\/1901.05594, 2019."},{"key":"atypb18","first-page":"497","volume":"6","author":"Dujmovi\u0107 V.","year":"2004","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb19","first-page":"339","volume":"6","author":"Dujmovi\u0107 V.","year":"2004","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"V. Dujmovi\u0107 and D. R. Wood,\n                      Three-dimensional Grid Drawings with Sub-quadratic Volume\n                      , in Towards a Theory of Geometric Graphs, Contemp. Math. 342, American Mathematical Society, Providence, RI, 2004,https:\/\/doi.org\/10.1090\/conm\/342\/06130.","DOI":"10.1090\/conm\/342\/06130"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.346"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00075"},{"key":"atypb23","unstructured":"J. L. Ganley,\n                      Stack and Queue Layouts of Halin Graphs\n                      , manuscript, 1995."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/0405031"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/0221055"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/0215057"},{"key":"atypb27","first-page":"459","volume":"8","author":"Ollmann T.","year":"1973","journal-title":"Congressus Numerantium"},{"key":"atypb28","unstructured":"S. V. Pemmaraju,\n                      Exploring the Powers of Stacks and Queues via Graph Layouts\n                      , Ph.D. thesis, Virginia Tech, Blacksburg, VA, 1992."},{"key":"atypb29","first-page":"197","author":"Pupyrev S.","year":"2017","journal-title":"Cham"},{"key":"atypb30","first-page":"203","author":"Rengarajan S.","year":"1995","journal-title":"Heidelberg"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321704"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.37236\/6429"},{"key":"atypb33","first-page":"27","volume":"10","author":"Wood D. R.","year":"2008","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90032-9"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M125340X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:05:33Z","timestamp":1787339133000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M125340X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/19M125340X"],"URL":"https:\/\/doi.org\/10.1137\/19m125340x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}