{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:21:35Z","timestamp":1787509295317,"version":"build-2736575974"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T00:00:00Z","timestamp":1664323200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T00:00:00Z","timestamp":1664323200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100021855","name":"University of Ioannina","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100021855","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    A\n                    <jats:italic>k<\/jats:italic>\n                    -queue layout is a special type of a linear layout, in which the linear order avoids\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$(k+1)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -rainbows, that is,\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$k+1$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    independent edges that pairwise form a nested pair. The optimization goal is to determine the\n                    <jats:italic>queue number<\/jats:italic>\n                    of a graph, which is defined as the minimum value of\n                    <jats:italic>k<\/jats:italic>\n                    for which a\n                    <jats:italic>k<\/jats:italic>\n                    -queue layout is feasible. Recently, Dujmovi\u0107 et al.\u00a0[J. ACM, 67(4), 22:1\u201338, 2020] showed that the queue number of planar graphs is at most 49, thus settling in the positive a long-standing conjecture by Heath, Leighton and Rosenberg. To achieve this breakthrough result, their approach involves three different techniques: (1)\u00a0an algorithm to obtain 2-queue layouts of outerplanar graphs, (2)\u00a0an algorithm to obtain 5-queue layouts of planar 3-trees, and (3)\u00a0a decomposition of a planar graph into so-called tripods. In this work, we push further each of these techniques to obtain the first non-trivial improvement of the upper bound on the queue number of planar graphs from 49 to\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$42 $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mn>42<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>","DOI":"10.1007\/s00453-022-01037-4","type":"journal-article","created":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T10:03:19Z","timestamp":1664359399000},"page":"544-562","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Improved Upper Bound on the Queue\u00a0Number of Planar Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3414-7444","authenticated-orcid":false,"given":"Michael","family":"Bekos","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Gronemann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chrysanthi N.","family":"Raftopoulou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,9,28]]},"reference":[{"issue":"3","key":"1037_CR1","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Petit, J., Serna, M.J.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313\u2013356 (2002). https:\/\/doi.org\/10.1145\/568522.568523","journal-title":"ACM Comput. Surv."},{"issue":"6","key":"1037_CR2","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1051\/ita\/1995290604871","volume":"29","author":"D Barth","year":"1995","unstructured":"Barth, D., Pellegrini, F., Raspaud, A., Roman, J.: On bandwidth, cutwidth, and quotient graphs. RAIRO Theor. Inform. Appl. 29(6), 487\u2013508 (1995). https:\/\/doi.org\/10.1051\/ita\/1995290604871","journal-title":"RAIRO Theor. Inform. Appl."},{"issue":"3","key":"1037_CR3","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/jgt.3190060302","volume":"6","author":"PZ Chinn","year":"1982","unstructured":"Chinn, P.Z., Chvatalova, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices - a survey. J. Graph Theory. 6(3), 223\u2013254 (1982). https:\/\/doi.org\/10.1002\/jgt.3190060302","journal-title":"J. Graph Theory."},{"issue":"1\u20133","key":"1037_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/S0166-218X(00)00173-6","volume":"103","author":"SB Horton","year":"2000","unstructured":"Horton, S.B., Parker, R.G., Borie, R.B.: On minimum cuts and the linear arrangement problem. Discret. Appl. Math. 103(1\u20133), 127\u2013139 (2000). https:\/\/doi.org\/10.1016\/S0166-218X(00)00173-6","journal-title":"Discret. Appl. Math."},{"key":"1037_CR5","doi-asserted-by":"crossref","unstructured":"Dujmovic, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar Graphs Have Bounded Queue-Number. J. ACM. 67(4):22:1\u201322:38 (2020)","DOI":"10.1145\/3385731"},{"issue":"3","key":"1037_CR6","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/0405031","volume":"5","author":"LS Heath","year":"1992","unstructured":"Heath, L.S., Leighton, F.T., Rosenberg, A.L.: Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Discrete Math. 5(3), 398\u2013412 (1992). https:\/\/doi.org\/10.1137\/0405031","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"1037_CR7","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). https:\/\/doi.org\/10.1137\/0221055","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1037_CR8","doi-asserted-by":"publisher","first-page":"P1.65","DOI":"10.37236\/6429","volume":"24","author":"V Wiechert","year":"2017","unstructured":"Wiechert, V.: On the queue-number of graphs with bounded tree-width. Electr. J. Comb. 24(1), P1.65 (2017)","journal-title":"Electr. J. Comb."},{"issue":"3","key":"1037_CR9","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/0095-8956(79)90021-2","volume":"27","author":"F Bernhart","year":"1979","unstructured":"Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Comb. Theory Ser. B. 27(3), 320\u2013331 (1979). https:\/\/doi.org\/10.1016\/0095-8956(79)90021-2","journal-title":"J. Comb. Theory Ser. B."},{"issue":"9","key":"1037_CR10","doi-asserted-by":"publisher","first-page":"2564","DOI":"10.1007\/s00453-020-00697-4","volume":"82","author":"JM Alam","year":"2020","unstructured":"Alam, J.M., Bekos, M.A., Gronemann, M., Kaufmann, M., Pupyrev, S.: Queue layouts of planar 3-trees. Algorithmica 82(9), 2564\u20132585 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00697-4","journal-title":"Algorithmica"},{"issue":"4","key":"1037_CR11","doi-asserted-by":"publisher","first-page":"1561","DOI":"10.1007\/s00453-018-0487-5","volume":"81","author":"MJ Bannister","year":"2019","unstructured":"Bannister, M.J., Devanny, W.E., Dujmovic, V., Eppstein, D., Wood, D.R.: Track layouts, layered path decompositions, and leveled planarity. Algorithmica 81(4), 1561\u20131583 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0487-5","journal-title":"Algorithmica"},{"issue":"5","key":"1037_CR12","doi-asserted-by":"publisher","first-page":"1487","DOI":"10.1137\/19M125340X","volume":"48","author":"MA Bekos","year":"2019","unstructured":"Bekos, M.A., F\u00f6rster, H., Gronemann, M., Mchedlidze, T., Montecchiani, F., Raftopoulou, C.N., et al.: Planar graphs of bounded degree have bounded queue number. SIAM J. Comput. 48(5), 1487\u20131502 (2019). https:\/\/doi.org\/10.1137\/19M125340X","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1037_CR13","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). https:\/\/doi.org\/10.1137\/S0097539702416141","journal-title":"SIAM J. Comput."},{"key":"1037_CR14","doi-asserted-by":"crossref","unstructured":"Wood, D.R.: Queue layouts, tree-width, and three-dimensional graph drawing. In: Agrawal M, Seth A, editors. FST TCS. vol. 2556 of LNCS. Springer pp. 348\u2013359 (2002)","DOI":"10.1007\/3-540-36206-1_31"},{"issue":"2","key":"1037_CR15","first-page":"339","volume":"6","author":"V Dujmovi\u0107","year":"2004","unstructured":"Dujmovi\u0107, V., Wood, D.R.: On linear layouts of graphs. Discrete Math. Theor. Computer Sci. 6(2), 339\u2013358 (2004)","journal-title":"Discrete Math. Theor. Computer Sci."},{"issue":"6","key":"1037_CR16","doi-asserted-by":"publisher","first-page":"2243","DOI":"10.1137\/130908051","volume":"42","author":"G Di Battista","year":"2013","unstructured":"Di Battista, G., Frati, F., Pach, J.: On the queue number of planar graphs. SIAM J. Comput. 42(6), 2243\u20132285 (2013). https:\/\/doi.org\/10.1137\/130908051","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1037_CR17","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.: Stack and queue layouts via layered separators. J. Graph Algorithms Appl. 22(1), 89\u201399 (2018). https:\/\/doi.org\/10.7155\/jgaa.00454","journal-title":"J. Graph Algorithms Appl."},{"key":"1037_CR18","doi-asserted-by":"crossref","unstructured":"Dujmovi\u0107, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar graphs have bounded queue-number. In: Zuckerman, D. (ed.) FOCS, pp. 862\u2013875. IEEE Computer Society (2019)","DOI":"10.1109\/FOCS.2019.00056"},{"issue":"1","key":"1037_CR19","first-page":"332","volume":"11","author":"MA Bekos","year":"2020","unstructured":"Bekos, M.A., Kaufmann, M., Klute, F., Pupyrev, S., Raftopoulou, C.N., Ueckerdt, T.: Four pages are indeed necessary for planar graphs. J. Comput. Geom. 11(1), 332\u2013353 (2020)","journal-title":"J. Comput. Geom."},{"issue":"1","key":"1037_CR20","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M Yannakakis","year":"1989","unstructured":"Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38(1), 36\u201367 (1989). https:\/\/doi.org\/10.1016\/0022-0000(89)90032-9","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1037_CR21","first-page":"497","volume":"6","author":"V Dujmovi\u0107","year":"2004","unstructured":"Dujmovi\u0107, V., P\u00f3r, A., Wood, D.R.: Track layouts of graphs. Discrete Math. Theor. Computer Sci. 6(2), 497\u2013522 (2004)","journal-title":"Discrete Math. Theor. Computer Sci."},{"key":"1037_CR22","doi-asserted-by":"crossref","unstructured":"Heath, L.S.: Embedding planar graphs in seven pages. In: FOCS. IEEE Computer Society pp. 74\u201383 (1984)","DOI":"10.1109\/SFCS.1984.715903"},{"key":"1037_CR23","unstructured":"Kratochv\u00edl, J., Vaner, M.: A note on planar partial 3-trees (2012) CoRR arXiv:1210.8113"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01037-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01037-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01037-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,4]],"date-time":"2024-10-04T17:22:30Z","timestamp":1728062550000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01037-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,28]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1037"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01037-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,28]]},"assertion":[{"value":"8 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}]}}