{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T09:06:55Z","timestamp":1777540015722,"version":"3.51.4"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2020,3,23]],"date-time":"2020-03-23T00:00:00Z","timestamp":1584921600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,23]],"date-time":"2020-03-23T00:00:00Z","timestamp":1584921600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A <jats:italic>queue layout<\/jats:italic> of a graph <jats:italic>G<\/jats:italic> consists of a <jats:italic>linear order<\/jats:italic> of the vertices of <jats:italic>G<\/jats:italic> and a partition of the edges of <jats:italic>G<\/jats:italic> into <jats:italic>queues<\/jats:italic>, so that no two independent edges of the same queue are nested. The <jats:italic>queue number<\/jats:italic> of graph <jats:italic>G<\/jats:italic> is defined as the minimum number of queues required by any queue layout of <jats:italic>G<\/jats:italic>. In this paper, we continue the study of the queue number of planar 3-trees, which form a well-studied subclass of planar graphs. Prior to this work, it was known that the queue number of planar 3-trees is at most seven. In this work, we improve this upper bound to five. We also show that there exist planar 3-trees whose queue number is at least four. Notably, this is the first example of a planar graph with queue number greater than three.<\/jats:p>","DOI":"10.1007\/s00453-020-00697-4","type":"journal-article","created":{"date-parts":[[2020,3,23]],"date-time":"2020-03-23T13:03:10Z","timestamp":1584968590000},"page":"2564-2585","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Queue Layouts of Planar 3-Trees"],"prefix":"10.1007","volume":"82","author":[{"given":"Jawaherul Md.","family":"Alam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Bekos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Gronemann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Pupyrev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,3,23]]},"reference":[{"key":"697_CR1","doi-asserted-by":"publisher","unstructured":"Alam, J.M., Bekos, M.A., Gronemann, M., Kaufmann, M., Pupyrev, S.: Queue layouts of planar 3-trees. In: T.C. Biedl, A. Kerren (eds.) Graph Drawing and Network Visualization, vol. 11282 , LNCS, pp. 213\u2013226. Springer, Berlin (2018). https:\/\/doi.org\/10.1007\/978-3-030-04414-5_15","DOI":"10.1007\/978-3-030-04414-5_15"},{"issue":"5","key":"697_CR2","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., Ueckerdt, T.: 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":"1","key":"697_CR3","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1006\/jpdc.1996.0024","volume":"33","author":"SN Bhatt","year":"1996","unstructured":"Bhatt, S.N., Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Scheduling tree-dags using FIFO queues: a control-memory trade-off. J. Parallel Distrib. Comput. 33(1), 55\u201368 (1996). https:\/\/doi.org\/10.1006\/jpdc.1996.0024","journal-title":"J. Parallel Distrib. Comput."},{"key":"697_CR4","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)"},{"issue":"6","key":"697_CR5","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":"697_CR6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.comgeo.2004.11.003","volume":"32","author":"E Di Giacomo","year":"2005","unstructured":"Di Giacomo, E., Liotta, G., Meijer, H.: Computing straight-line 3D grid drawings of graphs in linear volume. Comput. Geom. 32(1), 26\u201358 (2005). https:\/\/doi.org\/10.1016\/j.comgeo.2004.11.003","journal-title":"Comput. Geom."},{"key":"697_CR7","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. Comb. Theory Ser. B 110, 79\u201389 (2015). https:\/\/doi.org\/10.1016\/j.jctb.2014.07.005","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"697_CR8","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":"697_CR9","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1109\/FOCS.2019.00056","DOI":"10.1109\/FOCS.2019.00056"},{"issue":"3","key":"697_CR10","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":"697_CR11","unstructured":"Dujmovi\u0107, V., P\u00f3r, A., Wood, D.R.: Track layouts of graphs. Discrete Math. Theoret. Comput. Sci., 6(2), 497\u2013522 (2004). http:\/\/dmtcs.episciences.org\/315"},{"key":"697_CR12","doi-asserted-by":"publisher","unstructured":"Dujmovi\u0107, V., Wood, D.R.: Tree-partitions of k-trees with applications in graph layout. In: Bodlaender, H.L. (ed.) WG, vol. 2880 LNCS, pp. 205\u2013217. Springer, Berlin (2003). https:\/\/doi.org\/10.1007\/978-3-540-39890-5_18","DOI":"10.1007\/978-3-540-39890-5_18"},{"key":"697_CR13","unstructured":"Dujmovi\u0107, V., Wood, D.R.: Stacks, queues and tracks: layouts of graph subdivisions. Discrete Math. Theoret. Comput. Sci., 7(1), 155\u2013202 (2005). http:\/\/dmtcs.episciences.org\/346"},{"issue":"4","key":"697_CR14","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. Gr. Algorithms Appl. 7(4), 363\u2013398 (2003). https:\/\/doi.org\/10.7155\/jgaa.00075","journal-title":"J. Gr. Algorithms Appl."},{"key":"697_CR15","doi-asserted-by":"publisher","unstructured":"Fertin, G., Raspaud, A., Reed, B.A.: On star coloring of graphs. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG, vol. 2204 of LNCS, pp. 140\u2013153. Springer, Berlin (2001). https:\/\/doi.org\/10.1007\/3-540-45477-2_14","DOI":"10.1007\/3-540-45477-2_14"},{"key":"697_CR16","volume-title":"Graph Theory","author":"F Harary","year":"1972","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading, MA (1972)"},{"key":"697_CR17","doi-asserted-by":"publisher","unstructured":"Hasunuma, T.: Laying out iterated line digraphs using queues. In: Liotta, G. (ed.) Graph Drawing, volume 2912 of LNCS, pp. 202\u2013213. Springer, Berlin (2003). https:\/\/doi.org\/10.1007\/978-3-540-24595-7_19","DOI":"10.1007\/978-3-540-24595-7_19"},{"issue":"3","key":"697_CR18","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":"697_CR19","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."},{"key":"697_CR20","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., Wagner, D. (eds).: Drawing Graphs, Methods and Models, volume 2025 of LNCS. Springer, Berlin (2001)","DOI":"10.1007\/3-540-44969-8"},{"issue":"2","key":"697_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.7155\/jgaa.00222","volume":"15","author":"D Mondal","year":"2011","unstructured":"Mondal, D., Nishat, R.I., Rahman, M.S., Alam, M.J.: Minimum-area drawings of plane 3-trees. J. Gr. Algorithms Appl. 15(2), 177\u2013204 (2011). https:\/\/doi.org\/10.7155\/jgaa.00222","journal-title":"J. Gr. Algorithms Appl."},{"key":"697_CR22","unstructured":"Ollmann, T.: On the book thicknesses of various graphs. In Hoffman, F., Levow, R., Thomas, R. (eds.) Southeastern Conference on Combinatorics, Graph Theory and Computing, volume VIII of Congressus Numerantium, p. 459 (1973)"},{"key":"697_CR23","doi-asserted-by":"publisher","unstructured":"Pach, J., Thiele, T., T\u00f3th, G.: Three-dimensional grid drawings of graphs. In Di Battista, G. (ed.) Graph Drawing, volume 1353 of LNCS, pp. 47\u201351. Springer, Berlin (1997). https:\/\/doi.org\/10.1007\/3-540-63938-1_49","DOI":"10.1007\/3-540-63938-1_49"},{"key":"697_CR24","unstructured":"Pemmaraju, S.V.: Exploring the powers of stacks and queues via graph layouts. PhD thesis, Virginia Tech (1992)"},{"key":"697_CR25","doi-asserted-by":"publisher","unstructured":"Pupyrev, S.: Mixed linear layouts of planar graphs. In: Graph Drawing, volume 10692 of LNCS, pp. 197\u2013209. Springer, Berlin (2017). https:\/\/doi.org\/10.1007\/978-3-319-73915-1_17","DOI":"10.1007\/978-3-319-73915-1_17"},{"key":"697_CR26","unstructured":"Pupyrev, S.: Improved bounds for track numbers of planar graphs. CoRR, 1910.14153, (2019). https:\/\/arxiv.org\/abs\/1910.14153"},{"key":"697_CR27","doi-asserted-by":"publisher","unstructured":"Rengarajan, S., Madhavan, C.E.V.: Stack and queue number of 2-trees. In: Du, D., Li, M. (eds.) COCOON, volume 959 of LNCS, pp. 203\u2013212. Springer, Berlin (1995). https:\/\/doi.org\/10.1007\/BFb0030834","DOI":"10.1007\/BFb0030834"},{"issue":"1","key":"697_CR28","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1006\/jagm.1999.1049","volume":"34","author":"F Shahrokhi","year":"2000","unstructured":"Shahrokhi, F., Shi, W.: On crossing sets, disjoint sets, and pagenumber. J. Algorithms 34(1), 40\u201353 (2000). https:\/\/doi.org\/10.1006\/jagm.1999.1049","journal-title":"J. Algorithms"},{"issue":"2","key":"697_CR29","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/321694.321704","volume":"19","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Sorting using networks of queues and stacks. J. ACM 19(2), 341\u2013346 (1972). https:\/\/doi.org\/10.1145\/321694.321704","journal-title":"J. ACM"},{"key":"697_CR30","unstructured":"Wiechert, V.: On the queue-number of graphs with bounded tree-width. Electr. J. Comb., 24(1), P1.65, (2017). http:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v24i1p65"},{"key":"697_CR31","doi-asserted-by":"publisher","unstructured":"Wood, D.R.: Queue layouts, tree-width, and three-dimensional graph drawing. In: Agrawal, M., Seth, A. (eds.) FSTTCS, volume 2556 of LNCS, pp. 348\u2013359. Springer, Berlin (2002). https:\/\/doi.org\/10.1007\/3-540-36206-1_31","DOI":"10.1007\/3-540-36206-1_31"},{"issue":"1","key":"697_CR32","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."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00697-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00697-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00697-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T00:32:18Z","timestamp":1616459538000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00697-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,23]]},"references-count":32,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["697"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00697-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,23]]},"assertion":[{"value":"6 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}