{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:48:46Z","timestamp":1767340126993},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T00:00:00Z","timestamp":1630368000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T00:00:00Z","timestamp":1630368000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s00493-021-4585-7","type":"journal-article","created":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T14:04:40Z","timestamp":1630418680000},"page":"151-164","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Stack-Number is Not Bounded by Queue-Number"],"prefix":"10.1007","volume":"42","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Hickingbotham","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,31]]},"reference":[{"key":"4585_CR1","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.jda.2011.12.015","volume":"14","author":"P Angelini","year":"2012","unstructured":"P. Angelini, G. Di Battista, F. Frati, M. Patrignani and I. Rutter: Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph, J. Discrete Algorithms 14 (2012), 150\u2013172.","journal-title":"J. Discrete Algorithms"},{"key":"4585_CR2","doi-asserted-by":"crossref","unstructured":"M. Baur and U. Brandes: Crossing reduction in circular layouts, in: Proc. 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u2019 04), vol. 3353 of Lecture Notes in Computer Science, 332\u2013343, Springer, 2004.","DOI":"10.1007\/978-3-540-30559-0_28"},{"key":"4585_CR3","doi-asserted-by":"publisher","first-page":"1487","DOI":"10.1137\/19M125340X","volume":"48","author":"M A Bekos","year":"2019","unstructured":"M. A. Bekos, H. F\u00f6rster, M. Gronemann, T. Mchedlidze, F. Montecchiani, C. N. Raftopoulou and T. Ueckerdt: Planar graphs of bounded degree have bounded queue number, SIAM J. Comput. 48 (2019), 1487\u20131502.","journal-title":"SIAM J. Comput."},{"key":"4585_CR4","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/0095-8956(79)90021-2","volume":"27","author":"F R Bernhart","year":"1979","unstructured":"F. R. Bernhart and P. C. Kanen: The book thickness of a graph, J. Combin. Theory Ser. B 27 (1979), 320\u2013331.","journal-title":"J. Combin. Theory Ser. B"},{"key":"4585_CR5","series-title":"Ph.D. thesis","volume-title":"Book embeddings of graphs","author":"R Blankenship","year":"2003","unstructured":"R. Blankenship: Book embeddings of graphs, Ph.D. thesis, Department of Mathematics, Louisiana State University, U.S.A., 2003."},{"key":"4585_CR6","series-title":"Tech. Rep. 1999-4","volume-title":"Drawing subdivisions of complete and complete bipartite graphs on books","author":"R Blankenship","year":"1999","unstructured":"R. Blankenship and B. Oporowski: Drawing subdivisions of complete and complete bipartite graphs on books, Tech. Rep. 1999-4, Department of Mathematics, Louisiana State University, U.S.A., 1999."},{"key":"4585_CR7","doi-asserted-by":"crossref","unstructured":"\u00c9. Bonnet, C. Geniet, E. J. Kim, S. Thomass\u00e9 and R. Watrigant: Twin-width II: small classes, in: Proc. Annual ACM-SIAM Symp. on Discrete Algorithms (SODA\u2019 21), 2020.","DOI":"10.1137\/1.9781611976465.118"},{"key":"4585_CR8","unstructured":"\u00c9. Bonnet, C. Geniet, \u00c9. J. Kim, S. Thomass\u00e9 and R. Watrigant: Twin-width III: Max independent set and coloring, 2020, arXiv:2007.14161."},{"key":"4585_CR9","doi-asserted-by":"crossref","unstructured":"\u00c9. Bonnet, \u00c9. J. Kim, S. Thomass\u00e9 and R. Watrigant: Twin-width I: tractable FO model checking, in: Proc. 61st IEEE Symp. on Foundations of Comput. Sci. (FOCS\u2019 20). 2020.","DOI":"10.1109\/FOCS46700.2020.00062"},{"key":"4585_CR10","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.crma.2009.02.009","volume":"347","author":"J Bourgain","year":"2009","unstructured":"J. Bourgain: Expanders and dimensional expansion, C. R. Math. Acad. Sci. Paris 347 (2009), 357\u2013362.","journal-title":"C. R. Math. Acad. Sci. Paris"},{"key":"4585_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00039-012-0200-9","volume":"23","author":"J Bourgain","year":"2013","unstructured":"J. Bourgain and A. Yehudayoff: Expansion in SL2(\u211d) and monotone expansion, Geometric and Functional Analysis 23 (2013), 1\u201341.","journal-title":"Geometric and Functional Analysis"},{"key":"4585_CR12","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0608002","volume":"8","author":"F R K Chung","year":"1987","unstructured":"F. R. K. Chung, F. T. Leighton and A. L. Rosenberg: Embedding graphs in books: a layout problem with applications to VLSI design, SIAM J. Algebraic Discrete Methods 8 (1987), 33\u201358.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"4585_CR13","doi-asserted-by":"publisher","first-page":"2243","DOI":"10.1137\/130908051","volume":"42","author":"G Di Battista","year":"2013","unstructured":"G. Di Battista, F. Frati and J. Pach: On the queue number of planar graphs, SIAM J. Comput. 42 (2013), 2243\u20132285.","journal-title":"SIAM J. Comput."},{"key":"4585_CR14","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/3385731","volume":"67","author":"V Dujmovi\u0107","year":"2020","unstructured":"V. Dujmovi\u0107, G. Joret, P. Micek, P. Morin, T. Ueckerdt and D. R. Wood: Planar graphs have bounded queue-number, J. ACM 67 (2020), 22.","journal-title":"J. ACM"},{"key":"4585_CR15","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1137\/S0097539702416141","volume":"34","author":"V Dujmovi\u0107","year":"2005","unstructured":"V. Dujmovi\u0107, P. Morin and D. R. Wood: Layout of graphs with bounded tree-width, SIAM J. Comput. 34 (2005), 553\u2013579.","journal-title":"SIAM J. Comput."},{"key":"4585_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.jctb.2017.05.006","volume":"127","author":"V Dujmovi\u0107","year":"2017","unstructured":"V. Dujmovi\u0107, P. Morin and D. R. Wood: Layered separators in minor-closed graph classes with applications, J. Combin. Theory Ser. B 127 (2017), 111\u2013147.","journal-title":"J. Combin. Theory Ser. B"},{"key":"4585_CR17","unstructured":"V. Dujmovi\u0107, P. Morin and D. R. Wood: Graph product structure for non-minor-closed classes, 2019, arXiv:1907.05168."},{"key":"4585_CR18","first-page":"497","volume":"6","author":"V Dujmovi\u0107","year":"2004","unstructured":"V. Dujmovi\u0107, A. P\u00f3r and D. R. Wood: Track layouts of graphs, Discrete Math. Theor. Comput. Sci. 6 (2004), 497\u2013522.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"4585_CR19","unstructured":"V. Dujmovi\u0107, A. Sidiropoulos and D. R. Wood: Layouts of expander graphs, Chicago J. Theoret. Comput. Sci. 2016 (2016)."},{"key":"4585_CR20","first-page":"339","volume":"6","author":"V Dujmovi\u0107","year":"2004","unstructured":"V. Dujmovi\u0107 and D. R. Wood: On linear layouts of graphs, Discrete Math. Theor. Comput. Sci. 6 (2004), 339\u2013358.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"4585_CR21","doi-asserted-by":"publisher","first-page":"155","DOI":"10.46298\/dmtcs.346","volume":"7","author":"V Dujmovi\u0107","year":"2005","unstructured":"V. Dujmovi\u0107 and D. R. Wood: Stacks, queues and tracks: Layouts of graph subdivisions, Discrete Math. Theor. Comput. Sci. 7 (2005), 155\u2013202.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"4585_CR22","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00454-007-1318-7","volume":"37","author":"V Dujmovi\u0107","year":"2007","unstructured":"V. Dujmovi\u0107 and D. R. Wood: Graph treewidth and geometric thickness parameters, Discrete Comput. Geom. 37 (2007), 641\u2013670.","journal-title":"Discrete Comput. Geom."},{"key":"4585_CR23","doi-asserted-by":"crossref","unstructured":"Z. Dvo\u0159\u00e1k, T. Huynh, G. Joret, C.-H. Liu and D. R. Wood: Notes on graph product structure theory, in: D. R. Wood, J. de Gier, C. E. Praeger and T. Tao, eds., 2019-20 MATRIX Annals, 513\u2013533, Springer, 2021.","DOI":"10.1007\/978-3-030-62497-2_32"},{"key":"4585_CR24","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"P. Erd\u0151s and G. Szekeres: A combinatorial problem in geometry, Compositio Math. 2 (1935), 463\u2013470.","journal-title":"Compositio Math."},{"key":"4585_CR25","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1080\/00029890.1979.11994922","volume":"86","author":"D Gale","year":"1979","unstructured":"D. Gale: The game of Hex and the Brouwer fixed-point theorem, Amer. Math. Monthly 86 (1979), 818\u2013827.","journal-title":"Amer. Math. Monthly"},{"key":"4585_CR26","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/BF02122679","volume":"9","author":"Z Galil","year":"1989","unstructured":"Z. Galil, R. Kannan and E. Szemer\u00e9di: On 3-pushdown graphs with large separators, Combinatorica 9 (1989), 9\u201319.","journal-title":"Combinatorica"},{"key":"4585_CR27","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1006\/bulm.1998.0085","volume":"61","author":"C Haslinger","year":"1999","unstructured":"C. Haslinger and P. F. Stadler: RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties, Bull. Math. Biology 61 (1999), 437\u2013467.","journal-title":"Bull. Math. Biology"},{"key":"4585_CR28","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/0405031","volume":"5","author":"L S Heath","year":"1992","unstructured":"L. S. Heath, F. T. Leighton and A. L. Rosenberg: Comparing queues and stacks as mechanisms for laying out graphs, SIAM J. Discrete Math. 5 (1992), 398\u2013412.","journal-title":"SIAM J. Discrete Math."},{"key":"4585_CR29","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1137\/0221055","volume":"21","author":"L S Heath","year":"1992","unstructured":"L. S. Heath and A. L. Rosenberg: Laying out graphs using queues, SIAM J. Comput. 21 (1992), 927\u2013958.","journal-title":"SIAM J. Comput."},{"key":"4585_CR30","first-page":"332","volume":"11","author":"M Kaufmann","year":"2020","unstructured":"M. Kaufmann, M. A. Bekos, F. Klute, S. Pupyrev, C. N. Raftopoulou and T. Ueckerdt: Four pages are indeed necessary for planar graphs, J. Comput. Geom. 11 (2020), 332\u2013353.","journal-title":"J. Comput. Geom."},{"key":"4585_CR31","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1006\/jagm.1994.1027","volume":"17","author":"S M Malitz","year":"1994","unstructured":"S. M. Malitz: Graphs with E edges have pagenumber $$O(\\sqrt E )$$, J. Algorithms 17 (1994), 71\u201384.","journal-title":"J. Algorithms"},{"key":"4585_CR32","doi-asserted-by":"crossref","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez: Sparsity, vol. 28 of Algorithms and Combinatorics, Springer, 2012.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"4585_CR33","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1016\/j.ejc.2011.09.008","volume":"33","author":"J Ne\u0161et\u0159il","year":"2011","unstructured":"J. Ne\u0161et\u0159il, P. Ossona de Mendez and D. R. Wood: Characterisations and examples of graph classes with bounded expansion, European J. Combin. 33 (2011), 350\u2013373.","journal-title":"European J. Combin."},{"key":"4585_CR34","unstructured":"L. Taylor Ollmann: On the book thicknesses of various graphs, in: F. Hoffman, R. B. Levow and R. S. D. Thomas, eds., Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. VIII of Congr. Numer., 459, Utilitas Math., 1973."},{"key":"4585_CR35","unstructured":"S. Pupyrev: Book embeddings of graph products, 2020, arXiv:2007.15102."},{"key":"4585_CR36","doi-asserted-by":"publisher","first-page":"902","DOI":"10.1109\/TC.1983.1676134","volume":"C-32","author":"A L Rosenberg","year":"1983","unstructured":"A. L. Rosenberg: The DIOGENES approach to testable fault-tolerant arrays of processors, IEEE Trans. Comput. C-32 (1983), 902\u2013910.","journal-title":"IEEE Trans. Comput."},{"key":"4585_CR37","unstructured":"A. L. Rosenberg: Book embeddings and wafer-scale integration, in: Proc. 17th Southeastern International Conf. on Combinatorics, Graph Theory, and Computing, vol. 54 of Congr. Numer., 217\u2013224. 1986."},{"key":"4585_CR38","doi-asserted-by":"crossref","unstructured":"A. L. Rosenberg: DIOGENES, circa 1986, in: Proc. VLSI Algorithms and Architectures, vol. 227 of Lecture Notes in Comput. Sci., 96\u2013107, Springer, 1986.","DOI":"10.1007\/3-540-16766-8_9"},{"key":"4585_CR39","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1002\/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.0.CO;2-S","volume":"21","author":"F Shahrokhi","year":"1996","unstructured":"F. Shahrokhi, O. S\u00fdkora, L. A. Sz\u00e9kely and I. V\u0159\u0165o: The book crossing number of a graph, J. Graph Theory 21 (1996), 413\u2013424.","journal-title":"J. Graph Theory"},{"key":"4585_CR40","doi-asserted-by":"crossref","unstructured":"D. R. Wood: Bounded degree book embeddings and three-dimensional orthogonal graph drawing, in: P. Mutzel, M. J\u00fcnger and S. Leipert, eds., Proc. 9th International Symposium on Graph Drawing (GD\u2019 01), vol. 2265 of Lecture Notes in Computer Science, 312\u2013327, Springer, 2001.","DOI":"10.1007\/3-540-45848-4_25"},{"key":"4585_CR41","first-page":"255","volume":"7","author":"D R Wood","year":"2005","unstructured":"D. R. Wood: Queue layouts of graph products and powers, Discrete Math. Theor. Comput. Sci. 7 (2005), 255\u2013268.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"4585_CR42","first-page":"27","volume":"10","author":"D R Wood","year":"2008","unstructured":"D. R. Wood: Bounded-degree graphs have arbitrarily large queue-number, Discrete Math. Theor. Comput. Sci. 10 (2008), 27\u201334.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"4585_CR43","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M Yannakakis","year":"1989","unstructured":"M. Yannakakis: Embedding planar graphs in four pages, J. Comput. System Sci. 38 (1989), 36\u201367.","journal-title":"J. Comput. System Sci."},{"key":"4585_CR44","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.jctb.2020.05.008","volume":"145","author":"M Yannakakis","year":"2020","unstructured":"M. Yannakakis: Planar graphs that need four pages, J. Combin. Theory Ser. B 145 (2020), 241\u2013263.","journal-title":"J. Combin. Theory Ser. B"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-021-4585-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-021-4585-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-021-4585-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,21]],"date-time":"2022-05-21T12:05:58Z","timestamp":1653134758000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-021-4585-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,31]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["4585"],"URL":"https:\/\/doi.org\/10.1007\/s00493-021-4585-7","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,31]]},"assertion":[{"value":"9 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}