{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:19Z","timestamp":1740109339613,"version":"3.37.3"},"reference-count":94,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T00:00:00Z","timestamp":1689292800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T00:00:00Z","timestamp":1689292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN 20174LF3T8","PRIN 20157EFM5C","JMP N. 34120"],"award-info":[{"award-number":["PRIN 20174LF3T8","PRIN 20157EFM5C","JMP N. 34120"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["project 734922"],"award-info":[{"award-number":["project 734922"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A <jats:italic>k<\/jats:italic>-<jats:italic>page upward book embedding<\/jats:italic> (<jats:italic>k<\/jats:italic>UBE) of a directed acyclic graph\u00a0<jats:italic>G<\/jats:italic> is a book embeddings of\u00a0<jats:italic>G<\/jats:italic> on <jats:italic>k<\/jats:italic> pages with the additional requirement that the vertices appear in a topological ordering along the spine of the book. The <jats:italic>k<\/jats:italic><jats:sc>UBE Testing<\/jats:sc> problem, which asks whether a graph admits a <jats:italic>k<\/jats:italic>UBE, was introduced in 1999 by Heath, Pemmaraju, and Trenk (SIAM J Comput 28(4), 1999). In a companion paper, Heath and Pemmaraju (SIAM J Comput 28(5), 1999) proved that the problem is linear-time solvable for <jats:inline-formula><jats:alternatives><jats:tex-math>$$k=1$$<\/jats:tex-math><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><\/jats:alternatives><\/jats:inline-formula> and NP-complete for <jats:inline-formula><jats:alternatives><jats:tex-math>$$k = 6$$<\/jats:tex-math><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>6<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Closing this gap has been a central question in algorithmic graph theory since then. In this paper, we make a major contribution towards a definitive answer to the above question by showing that <jats:italic>k<\/jats:italic><jats:sc>UBE Testing<\/jats:sc> is NP-complete for <jats:inline-formula><jats:alternatives><jats:tex-math>$$k\\ge 3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, even for <jats:italic>st<\/jats:italic>-graphs, i.e., acyclic directed graphs with a single source and a single sink. Indeed, our result, together with a recent work of Bekos et al. (Theor Comput Sci 946, 2023) that proves the NP-completeness of 2UBE for planar <jats:italic>st<\/jats:italic>-graphs, closes the question about the complexity of the <jats:italic>k<\/jats:italic>UBE problem for any <jats:italic>k<\/jats:italic>. Motivated by this hardness result, we then focus on the 2UBE <jats:sc>Testing<\/jats:sc> for planar <jats:italic>st<\/jats:italic>-graphs. On the algorithmic side, we present an <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(f(\\beta )\\cdot n+n^3)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>\u03b2<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithm for 2UBE <jats:sc>Testing<\/jats:sc>, where <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\beta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b2<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the branchwidth of the input graph and <jats:italic>f<\/jats:italic> is a singly-exponential function on <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\beta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b2<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Since the treewidth and the branchwidth of a graph are within a constant factor from each other, this result immediately yields an FPT algorithm for <jats:italic>st<\/jats:italic>-graphs of bounded treewidth. Furthermore, we describe an <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>)-time algorithm to test whether a plane <jats:italic>st<\/jats:italic>-graph whose faces have a special structure admits a 2UBE that additionally preserves the plane embedding of the input <jats:italic>st<\/jats:italic>-graph. On the combinatorial side, we present two notable families of plane <jats:italic>st<\/jats:italic>-graphs that always admit an embedding-preserving <jats:inline-formula><jats:alternatives><jats:tex-math>$$2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>UBE.<\/jats:p>","DOI":"10.1007\/s00453-023-01142-y","type":"journal-article","created":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T09:01:31Z","timestamp":1689325291000},"page":"3521-3571","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Upward Book Embeddability of st-Graphs: Complexity and Algorithms"],"prefix":"10.1007","volume":"85","author":[{"given":"Carla","family":"Binucci","sequence":"first","affiliation":[]},{"given":"Giordano","family":"Da Lozzo","sequence":"additional","affiliation":[]},{"given":"Emilio","family":"Di Giacomo","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4379-6059","authenticated-orcid":false,"given":"Walter","family":"Didimo","sequence":"additional","affiliation":[]},{"given":"Tamara","family":"Mchedlidze","sequence":"additional","affiliation":[]},{"given":"Maurizio","family":"Patrignani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,14]]},"reference":[{"key":"1142_CR1","unstructured":"\u00c1brego, B.M., Aichholzer, O., Fern\u00e1ndez-Merchant, S., Ramos, P., Salazar, G.: The 2-page crossing number of $$K_n$$. In: T.\u00a0K. Dey and S.\u00a0Whitesides, editors, Symposium on Computational Geometry 2012, SoCG \u201912, pp. 397\u2013404. ACM, (2012)"},{"key":"1142_CR2","doi-asserted-by":"crossref","unstructured":"Akitaya, H.A. , Demaine, E.D., Hesterberg, A., Liu, Q.C.: Upward partitioned book embeddings. In: F.\u00a0Frati and K.\u00a0Ma, editors, GD 2017, volume 10692 of LNCS, pp. 210\u2013223. Springer, (2017)","DOI":"10.1007\/978-3-319-73915-1_18"},{"key":"1142_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2021.01.035","volume":"861","author":"MJ Alam","year":"2021","unstructured":"Alam, M.J., Bekos, M.A., Dujmovic, V., Gronemann, M., Kaufmann, M., Pupyrev, S.: On dispersable book embeddings. Theor. Comput. Sci. 861, 1\u201322 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"1142_CR4","first-page":"47","volume":"119","author":"M Alhashem","year":"2015","unstructured":"Alhashem, M., Jourdan, G., Zaguia, N.: On the book embedding of ordered sets. Ars Combin. 119, 47\u201364 (2015)","journal-title":"Ars Combin."},{"key":"1142_CR5","doi-asserted-by":"crossref","unstructured":"Alzohairi, M., Rival, I.: Series-parallel planar ordered sets have pagenumber two. In: S.\u00a0C. North, editor, Graph Drawing, GD \u201996, volume 1190 of LNCS, pp. 11\u201324. Springer, (1996)","DOI":"10.1007\/3-540-62495-3_34"},{"key":"1142_CR6","doi-asserted-by":"crossref","unstructured":"Angelini, P., Bekos, M.A., Didimo, W., Grilli, L., Kindermann, P., Mchedlidze, T., Prutkin, R., Symvonis, A., Tappini, A.: Greedy rectilinear drawings. In: Biedl, T., Kerren, A. (eds.) GD 2018, volume 11282 of LNCS. Springer, (2018)","DOI":"10.1007\/978-3-030-04414-5_35"},{"key":"1142_CR7","unstructured":"Angelini, P., Chaplick, S., Cornelsen, S., Da Lozzo, G.: On upward-planar L-drawings of graphs. In: Szeider, S., Ganian, R., Silva, A. (eds.) 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria, volume 241 of LIPIcs, pages 10:1\u201310:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2022)"},{"key":"1142_CR8","doi-asserted-by":"crossref","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Donato, V.\u00a0D., Kindermann, P., Rote, G., Rutter, I.: Windrose planarity: embedding graphs with direction-constrained edges. AMS Trans. Algorithms 14(4), 54:1-54:24 (2018)","DOI":"10.1145\/3239561"},{"issue":"4","key":"1142_CR9","doi-asserted-by":"crossref","first-page":"1022","DOI":"10.1007\/s00453-016-0128-9","volume":"77","author":"P Angelini","year":"2017","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F.: Strip planarity testing for embedded planar graphs. Algorithmica 77(4), 1022\u20131059 (2017)","journal-title":"Algorithmica"},{"key":"1142_CR10","doi-asserted-by":"crossref","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M.: 2-Level quasi-planarity or how caterpillars climb (SPQR-)trees. In: Marx, D. editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms. SODA 2021, Virtual Conference 2021, 2779\u20132798 (2021). (SIAM, , 10 - 13)","DOI":"10.1137\/1.9781611976465.165"},{"issue":"4","key":"1142_CR11","doi-asserted-by":"crossref","first-page":"731","DOI":"10.7155\/jgaa.00437","volume":"21","author":"P Angelini","year":"2017","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Intersection-link representations of graphs. J. Graph Algorithms Appl. 21(4), 731\u2013755 (2017)","journal-title":"J. Graph Algorithms Appl."},{"key":"1142_CR12","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.tcs.2014.11.016","volume":"575","author":"P Angelini","year":"2015","unstructured":"Angelini, P., Da Lozzo, G., Neuwirth, D.: Advancements on SEFE and partitioned book embedding problems. Theor. Comput. Sci. 575, 71\u201389 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"1142_CR13","doi-asserted-by":"crossref","unstructured":"Angelini, P., Di Bartolomeo, M., Di Battista, G.: Implementing a partitioned 2-page book embedding testing algorithm. In: Graph Drawing, volume of LNCS 7704, 79\u201389 (2012). (Springer)","DOI":"10.1007\/978-3-642-36763-2_8"},{"key":"1142_CR14","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/j.jda.2011.12.015","volume":"14","author":"P Angelini","year":"2012","unstructured":"Angelini, P., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph. J. Dis. Algorithms 14, 150\u2013172 (2012)","journal-title":"J. Dis. Algorithms"},{"issue":"3","key":"1142_CR15","doi-asserted-by":"crossref","first-page":"313","DOI":"10.7155\/jgaa.00324","volume":"18","author":"P Angelini","year":"2014","unstructured":"Angelini, P., Eppstein, D., Frati, F., Kaufmann, M., Lazard, S., Mchedlidze, T., Teillaud, M., Wolff, A.: Universal point sets for drawing planar graphs with circular arcs. J. Graph Algorithms Appl. 18(3), 313\u2013324 (2014)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2\u20133","key":"1142_CR16","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/j.tcs.2008.08.004","volume":"408","author":"M Badent","year":"2008","unstructured":"Badent, M., Di Giacomo, E., Liotta, G.: Drawing colored graphs on colored points. Theor. Comput. Sci. 408(2\u20133), 129\u2013142 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"1142_CR17","doi-asserted-by":"crossref","unstructured":"Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. In: Duncan, C.A., Symvonis, A. (eds.) GD 2014 8871, 210\u2013221 (2014). (LNCS,Springer)","DOI":"10.1007\/978-3-662-45803-7_18"},{"issue":"2","key":"1142_CR18","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1007\/s00453-016-0203-2","volume":"79","author":"MA Bekos","year":"2017","unstructured":"Bekos, M.A., Bruckdorfer, T., Kaufmann, M., Raftopoulou, C.N.: The book thickness of 1-planar graphs is constant. Algorithmica 79(2), 444\u2013465 (2017)","journal-title":"Algorithmica"},{"key":"1142_CR19","doi-asserted-by":"crossref","DOI":"10.1016\/j.tcs.2023.113689","volume":"946","author":"MA Bekos","year":"2023","unstructured":"Bekos, M.A., Da Lozzo, G., Frati, F., Gronemann, M., Mchedlidze, T., Raftopoulou, C.N.: Recognizing dags with page-number 2 is NP-complete. Theor. Comput. Sci. 946, 113689 (2023)","journal-title":"Theor. Comput. Sci."},{"key":"1142_CR20","doi-asserted-by":"crossref","unstructured":"Bekos, M.A., Da Lozzo, G., Frati, F., Gronemann, M., Mchedlidze, T., Raftopoulou, C.N.: Recognizing dags with page-number 2 is NP-complete. In: Angelini, P., von Hanxleden, R. (eds.) Graph Drawing and Network Visualization. pp, pp. 361\u2013370. Springer International Publishing, Cham (2023)","DOI":"10.1007\/978-3-031-22203-0_26"},{"key":"1142_CR21","unstructured":"Bekos, M.A., Da Lozzo, G., Griesbach, S., Gronemann, M., Montecchiani, F., Raftopoulou, C.N.: Book embeddings of nonplanar graphs with small faces in few pages. In: Cabello, S., Chen, D.Z., (eds.) 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Z\u00fcrich, Switzerland, volume 164 of LIPIcs, pages 16:1\u201316:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2020)"},{"key":"1142_CR22","doi-asserted-by":"crossref","unstructured":"Bekos, M.A., Di Giacomo, E., Didimo, W., Liotta, G., Montecchiani, F., Raftopoulou, C.N.: Edge partitions of optimal 2-plane and 3-plane graphs. In: Brandst\u00e4dt, A., K\u00f6hler, E., Meer, K., (eds.) Graph-Theoretic Concepts in Computer Science, WG 2018, volume 11159 of LNCS, pages 27\u201339. Springer, (2018)","DOI":"10.1007\/978-3-030-00256-5_3"},{"issue":"1","key":"1142_CR23","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/s00453-015-0016-8","volume":"75","author":"MA Bekos","year":"2016","unstructured":"Bekos, M.A., Gronemann, M., Raftopoulou, C.N.: Two-page book embeddings of 4-planar graphs. Algorithmica 75(1), 158\u2013185 (2016)","journal-title":"Algorithmica"},{"issue":"1","key":"1142_CR24","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":"3","key":"1142_CR25","doi-asserted-by":"crossref","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. Combinat. Theory, Series B 27(3), 320\u2013331 (1979)","journal-title":"J. Combinat. Theory, Series B"},{"issue":"3","key":"1142_CR26","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1007\/s00453-001-0083-x","volume":"32","author":"P Bertolazzi","year":"2002","unstructured":"Bertolazzi, P., Di Battista, G., Didimo, W.: Quasi-upward planarity. Algorithmica 32(3), 474\u2013506 (2002)","journal-title":"Algorithmica"},{"issue":"1","key":"1142_CR27","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1137\/S0097539794279626","volume":"27","author":"P Bertolazzi","year":"1998","unstructured":"Bertolazzi, P., Di Battista, G., Mannino, C., Tamassia, R.: Optimal upward planarity testing of single-source digraphs. SIAM J. Comput. 27(1), 132\u2013169 (1998)","journal-title":"SIAM J. Comput."},{"key":"1142_CR28","doi-asserted-by":"crossref","DOI":"10.1016\/j.ejc.2022.103662","volume":"110","author":"S Bhore","year":"2023","unstructured":"Bhore, S., Da Lozzo, G., Montecchiani, F., N\u00f6llenburg, M.: On the upward book thickness problem: combinatorial and complexity results. Eur. J. Comb. 110, 103662 (2023)","journal-title":"Eur. J. Comb."},{"issue":"4","key":"1142_CR29","doi-asserted-by":"crossref","first-page":"63","DOI":"10.7155\/jgaa.00018","volume":"3","author":"TC Biedl","year":"1999","unstructured":"Biedl, T.C., Shermer, T.C., Whitesides, S., Wismath, S.K.: Bounds for orthogonal 3-d graph drawing. J. Graph Algorithms Appl. 3(4), 63\u201379 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"1142_CR30","unstructured":"Binucci, C., Da Lozzo, G., Giacomo, E.D., Didimo, W., Mchedlidze, T., Patrignani, M.: Upward book embeddings of st-graphs. In: Barequet, G., Wang, Y., (eds.) 35th International Symposium on Computational Geometry, SoCG 2019, June 18-21, 2019, Portland, Oregon, USA, volume 129 of LIPIcs, pages 13:1\u201313:22. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, (2019)"},{"key":"1142_CR31","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/j.ejc.2017.07.009","volume":"68","author":"C Binucci","year":"2018","unstructured":"Binucci, C., Di Giacomo, E., Hossain, M.I., Liotta, G.: 1-page and 2-page drawings with bounded number of crossings per edge. Eur. J. Comb. 68, 24\u201337 (2018)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"1142_CR32","first-page":"133","volume":"59","author":"C Binucci","year":"2016","unstructured":"Binucci, C., Didimo, W.: Computing quasi-upward planar drawings of mixed graphs. Comput. J. 59(1), 133\u2013150 (2016)","journal-title":"Comput. J."},{"key":"1142_CR33","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.tcs.2014.01.015","volume":"526","author":"C Binucci","year":"2014","unstructured":"Binucci, C., Didimo, W., Patrignani, M.: Upward and quasi-upward planarity testing of embedded mixed graphs. Theor. Comput. Sci. 526, 75\u201389 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1142_CR34","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.comgeo.2013.08.003","volume":"47","author":"F Brandenburg","year":"2014","unstructured":"Brandenburg, F.: Upward planar drawings on the standing and the rolling cylinders. Comput. Geom. 47(1), 25\u201341 (2014)","journal-title":"Comput. Geom."},{"key":"1142_CR35","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.comgeo.2017.06.001","volume":"68","author":"J Cardinal","year":"2018","unstructured":"Cardinal, J., Hoffmann, M., Kusters, V., T\u00f3th, C.D., Wettstein, M.: Arc diagrams, flip distances, and hamiltonian triangulations. Comput. Geom. 68, 206\u2013225 (2018)","journal-title":"Comput. Geom."},{"key":"1142_CR36","doi-asserted-by":"crossref","unstructured":"Chaplick,S., Chimani, M., Cornelsen, S., Da Lozzo, G., N\u00f6llenburg, M., Patrignani, M., Tollis, I.G., Wolff, A.: Planar L-drawings of directed graphs. In: Frati, F., Ma, K., (eds.) GD 2017, volume 10692 of LNCS, pages 465\u2013478. Springer, (2017)","DOI":"10.1007\/978-3-319-73915-1_36"},{"issue":"1","key":"1142_CR37","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0608002","volume":"8","author":"FRK Chung","year":"1987","unstructured":"Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Embedding graphs in books: a layout problem with applications to VLSI design. SIAM J. Algebraic Dis. Methods 8(1), 33\u201358 (1987)","journal-title":"SIAM J. Algebraic Dis. Methods"},{"issue":"3","key":"1142_CR38","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s10732-006-4294-9","volume":"12","author":"RJ Cimikowski","year":"2006","unstructured":"Cimikowski, R.J.: An analysis of some linear graph layout heuristics. J. Heuristics 12(3), 143\u2013153 (2006)","journal-title":"J. Heuristics"},{"key":"1142_CR39","doi-asserted-by":"crossref","DOI":"10.1016\/j.comgeo.2020.101668","volume":"91","author":"G Da Lozzo","year":"2020","unstructured":"Da Lozzo, G., Di Battista, G., Frati, F.: Extending upward planar graph drawings. Comput. Geom. 91, 101668 (2020)","journal-title":"Comput. Geom."},{"issue":"10","key":"1142_CR40","doi-asserted-by":"crossref","first-page":"2985","DOI":"10.1007\/s00453-020-00714-6","volume":"82","author":"G Da Lozzo","year":"2020","unstructured":"Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Roselli, V.: Upward planar morphs. Algorithmica 82(10), 2985\u20133017 (2020)","journal-title":"Algorithmica"},{"key":"1142_CR41","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G Di Battista","year":"1998","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall PTR, USA (1998)"},{"key":"1142_CR42","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0304-3975(88)90123-5","volume":"61","author":"G Di Battista","year":"1988","unstructured":"Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci. 61, 175\u2013198 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"1142_CR43","doi-asserted-by":"crossref","first-page":"956","DOI":"10.1137\/S0097539794280736","volume":"25","author":"G Di Battista","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956\u2013997 (1996)","journal-title":"SIAM J. Comput."},{"key":"1142_CR44","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF02187850","volume":"7","author":"G Di Battista","year":"1992","unstructured":"Di Battista, G., Tamassia, R., Tollis, I.G.: Area requirement and symmetry display of planar upward drawings. Dis. Comput. Geomet. 7, 381\u2013401 (1992)","journal-title":"Dis. Comput. Geomet."},{"issue":"1","key":"1142_CR45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.comgeo.2004.04.002","volume":"30","author":"E Di Giacomo","year":"2005","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Curve-constrained drawings of planar graphs. Comput. Geom. 30(1), 1\u201323 (2005)","journal-title":"Comput. Geom."},{"issue":"4","key":"1142_CR46","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1007\/s00453-005-1185-7","volume":"45","author":"E Di Giacomo","year":"2006","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Book embeddability of series-parallel digraphs. Algorithmica 45(4), 531\u2013547 (2006)","journal-title":"Algorithmica"},{"issue":"2","key":"1142_CR47","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1137\/080731128","volume":"25","author":"E Di Giacomo","year":"2011","unstructured":"Di Giacomo, E., Giordano, F., Liotta, G.: Upward topological book embeddings of dags. SIAM J. Dis. Math. 25(2), 479\u2013489 (2011)","journal-title":"SIAM J. Dis. Math."},{"issue":"5","key":"1142_CR48","doi-asserted-by":"crossref","first-page":"1071","DOI":"10.1142\/S0129054106004273","volume":"17","author":"E Di Giacomo","year":"2006","unstructured":"Di Giacomo, E., Liotta, G., Trotta, F.: On embedding a graph on two sets of points. Int. J. Found. Comput. Sci. 17(5), 1071\u20131094 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"1142_CR49","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1007\/s00453-008-9255-2","volume":"57","author":"E Di Giacomo","year":"2010","unstructured":"Di Giacomo, E., Liotta, G., Trotta, F.: Drawing colored graphs with constrained vertex positions and few bends per edge. Algorithmica 57(4), 796\u2013818 (2010)","journal-title":"Algorithmica"},{"key":"1142_CR50","doi-asserted-by":"crossref","unstructured":"Didimo, W.: Upward graph drawing. In: Encyclopedia of Algorithms, pages 2308\u20132312. Springer, (2016)","DOI":"10.1007\/978-1-4939-2864-4_653"},{"issue":"4","key":"1142_CR51","doi-asserted-by":"crossref","first-page":"1842","DOI":"10.1137\/070696854","volume":"23","author":"W Didimo","year":"2009","unstructured":"Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. SIAM J. Dis. Math. 23(4), 1842\u20131899 (2009)","journal-title":"SIAM J. Dis. Math."},{"issue":"3","key":"1142_CR52","doi-asserted-by":"crossref","first-page":"790","DOI":"10.1007\/s00453-009-9296-1","volume":"58","author":"F Dorn","year":"2010","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica 58(3), 790\u2013810 (2010)","journal-title":"Algorithmica"},{"key":"1142_CR53","unstructured":"Dujmovic, V., Eppstein, D., Hickingbotham, R., Morin, P., Wood, D.R.: Stack-number is not bounded by queue-number. CoRR, abs\/2011.04195, (2020)"},{"issue":"2","key":"1142_CR54","first-page":"339","volume":"6","author":"V Dujmovi\u0107","year":"2004","unstructured":"Dujmovi\u0107, V., Wood, D.R.: On linear layouts of graphs. Dis. Math. Theor. Comput. Sci. 6(2), 339\u2013358 (2004)","journal-title":"Dis. Math. Theor. Comput. Sci."},{"issue":"1","key":"1142_CR55","first-page":"155","volume":"7","author":"V Dujmovi\u0107","year":"2005","unstructured":"Dujmovi\u0107, V., Wood, D.R.: Stacks, queues and tracks: layouts of graph subdivisions. Dis. Math. Theor. Comput. Sci. 7(1), 155\u2013202 (2005)","journal-title":"Dis. Math. Theor. Comput. Sci."},{"issue":"3","key":"1142_CR56","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1137\/S0895480195280319","volume":"12","author":"H Enomoto","year":"1999","unstructured":"Enomoto, H., Miyauchi, M.S.: Embedding graphs into a three page book with $$O(m \\log n)$$ crossings of edges over the spine. SIAM J. Dis. Math. 12(3), 337\u2013341 (1999)","journal-title":"SIAM J. Dis. Math."},{"issue":"2\u20133","key":"1142_CR57","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0166-218X(99)00044-X","volume":"92","author":"H Enomoto","year":"1999","unstructured":"Enomoto, H., Miyauchi, M.S., Ota, K.: Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph. Discret. Appl. Math. 92(2\u20133), 149\u2013155 (1999)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1142_CR58","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1006\/jctb.1997.1773","volume":"71","author":"H Enomoto","year":"1997","unstructured":"Enomoto, H., Nakamigawa, T., Ota, K.: On the pagenumber of complete bipartite graphs. J. Combinat. Theory, Series B 71(1), 111\u2013120 (1997)","journal-title":"J. Combinat. Theory, Series B"},{"issue":"2","key":"1142_CR59","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1007\/s00454-009-9149-3","volume":"43","author":"H Everett","year":"2010","unstructured":"Everett, H., Lazard, S., Liotta, G., Wismath, S.K.: Universal sets of $$n$$ points for one-bend drawings of planar graphs with $$n$$ vertices. Dis. Comput. Geomet. 43(2), 272\u2013288 (2010)","journal-title":"Dis. Comput. Geomet."},{"issue":"1","key":"1142_CR60","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1002\/jgt.20121","volume":"51","author":"FV Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. J. Graph Theory 51(1), 53\u201381 (2006)","journal-title":"J. Graph Theory"},{"issue":"3","key":"1142_CR61","doi-asserted-by":"crossref","first-page":"221","DOI":"10.7155\/jgaa.00292","volume":"17","author":"F Frati","year":"2013","unstructured":"Frati, F., Fulek, R., Ruiz-Vargas, A.J.: On the page number of upward planar directed acyclic graphs. J. Graph Algorithms and Appl. 17(3), 221\u2013244 (2013)","journal-title":"J. Graph Algorithms and Appl."},{"issue":"3","key":"1142_CR62","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0166-218X(00)00178-5","volume":"109","author":"JL Ganley","year":"2001","unstructured":"Ganley, J.L., Heath, L.S.: The pagenumber of $$k$$-trees is $$O(k)$$. Discret. Appl. Math. 109(3), 215\u2013221 (2001)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1142_CR63","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1137\/S0097539794277123","volume":"31","author":"A Garg","year":"2001","unstructured":"Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601\u2013625 (2001)","journal-title":"SIAM J. Comput."},{"key":"1142_CR64","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.jda.2014.11.006","volume":"30","author":"F Giordano","year":"2015","unstructured":"Giordano, F., Liotta, G., Mchedlidze, T., Symvonis, A., Whitesides, S.: Computing upward topological book embeddings of upward planar digraphs. J. Dis. Algorithms 30, 45\u201369 (2015)","journal-title":"J. Dis. Algorithms"},{"key":"1142_CR65","doi-asserted-by":"crossref","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed) Graph Drawing, GD 2000, volume 1984 of LNCS, pages 77\u201390. Springer, (2000)","DOI":"10.1007\/3-540-44541-2_8"},{"issue":"3","key":"1142_CR66","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1137\/0405031","volume":"5","author":"L Heath","year":"1992","unstructured":"Heath, L., Leighton, F., Rosenberg, A.: Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Dis. Math. 5(3), 398\u2013412 (1992)","journal-title":"SIAM J. Dis. Math."},{"issue":"4","key":"1142_CR67","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1137\/S0895480193252380","volume":"10","author":"LS Heath","year":"1997","unstructured":"Heath, L.S., Pemmaraju, S.V.: Stack and queue layouts of posets. SIAM J. Dis. Math. 10(4), 599\u2013625 (1997)","journal-title":"SIAM J. Dis. Math."},{"issue":"5","key":"1142_CR68","doi-asserted-by":"crossref","first-page":"1588","DOI":"10.1137\/S0097539795291550","volume":"28","author":"LS Heath","year":"1999","unstructured":"Heath, L.S., Pemmaraju, S.V.: Stack and queue layouts of directed acyclic graphs: Part II. SIAM J. Comput. 28(5), 1588\u20131626 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1142_CR69","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.1137\/S0097539795280287","volume":"28","author":"LS Heath","year":"1999","unstructured":"Heath, L.S., Pemmaraju, S.V., Trenk, A.N.: Stack and queue layouts of directed acyclic graphs: Part I. SIAM J. Comput. 28(4), 1510\u20131539 (1999)","journal-title":"SIAM J. Comput."},{"key":"1142_CR70","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.tcs.2015.12.039","volume":"725","author":"S Hong","year":"2018","unstructured":"Hong, S., Nagamochi, H.: Simpler algorithms for testing two-page book embedding of partitioned graphs. Theor. Comput. Sci. 725, 79\u201398 (2018)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1142_CR71","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2(3), 135\u2013158 (1973)","journal-title":"SIAM J. Comput."},{"key":"1142_CR72","unstructured":"Hung, L.T.Q.: A Planar Poset which Requires 4 Pages. PhD thesis, Institute of Computer Science, University of Wroc\u0142aw, (1989)"},{"key":"1142_CR73","doi-asserted-by":"crossref","unstructured":"Jungeblut, P., Merker, L., Ueckerdt, T.: A sublinear bound on the page number of upward planar graphs. In: J.\u00a0S. Naor and N.\u00a0Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference \/ Alexandria, VA, USA, January 9 - 12, 2022, pages 963\u2013978. SIAM, (2022)","DOI":"10.1137\/1.9781611977073.42"},{"key":"1142_CR74","unstructured":"Kleinberg, J.M., Tardos, \u00c9.: Algorithm design. Addison-Wesley, (2006)"},{"key":"1142_CR75","doi-asserted-by":"crossref","unstructured":"L\u00f6ffler, M., T\u00f3th, C.D.: Linear-size universal point sets for one-bend drawings. In: Graph Drawing, volume 9411 of LNCS, pages 423\u2013429. Springer, (2015)","DOI":"10.1007\/978-3-319-27261-0_35"},{"issue":"1","key":"1142_CR76","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1006\/jagm.1994.1028","volume":"17","author":"SM Malitz","year":"1994","unstructured":"Malitz, S.M.: Genus $$g$$ graphs have pagenumber $$O(\\sqrt{g})$$. J. Algorithms 17(1), 85\u2013109 (1994)","journal-title":"J. Algorithms"},{"issue":"1","key":"1142_CR77","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1006\/jagm.1994.1027","volume":"17","author":"SM Malitz","year":"1994","unstructured":"Malitz, S.M.: Graphs with $$E$$ edges have pagenumber $$O(\\sqrt{E})$$. J. Algorithms 17(1), 71\u201384 (1994)","journal-title":"J. Algorithms"},{"issue":"1","key":"1142_CR78","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1109\/12.46286","volume":"39","author":"S Masuda","year":"1990","unstructured":"Masuda, S., Nakajima, K., Kashiwabara, T., Fujisawa, T.: Crossing minimization in linear embeddings of graphs. IEEE Trans. Comput. 39(1), 124\u2013127 (1990)","journal-title":"IEEE Trans. Comput."},{"key":"1142_CR79","doi-asserted-by":"crossref","unstructured":"Mchedlidze, T., Symvonis, A.: Crossing-free acyclic hamiltonian path completion for planar $${st}$$-digraphs. In: Dong, Y., Du, D., Ibarra, O.H., (eds.) Algorithms and Computation, ISAAC 2009, volume 5878 of LNCS, pages 882\u2013891. Springer, (2009)","DOI":"10.1007\/978-3-642-10631-6_89"},{"key":"1142_CR80","doi-asserted-by":"crossref","unstructured":"Mchedlidze, T., Symvonis, A.: Unilateral orientation of mixed graphs. In: SOFSEM 2010, volume 5901 of LNCS, pages 588\u2013599. Springer, (2010)","DOI":"10.1007\/978-3-642-11266-9_49"},{"issue":"3","key":"1142_CR81","doi-asserted-by":"crossref","first-page":"373","DOI":"10.7155\/jgaa.00231","volume":"15","author":"T Mchedlidze","year":"2011","unstructured":"Mchedlidze, T., Symvonis, A.: Crossing-optimal acyclic HP-completion for outerplanar st-digraphs. J. Graph Algorithms and Appl. 15(3), 373\u2013415 (2011)","journal-title":"J. Graph Algorithms and Appl."},{"issue":"3","key":"1142_CR82","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF00563521","volume":"6","author":"R Nowakowski","year":"1989","unstructured":"Nowakowski, R., Parker, A.: Ordered sets, pagenumbers and planarity. Order 6(3), 209\u2013218 (1989)","journal-title":"Order"},{"issue":"1","key":"1142_CR83","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0208008","volume":"8","author":"J Opatrny","year":"1979","unstructured":"Opatrny, J.: Total ordering problem. SIAM J. Comput. 8(1), 111\u2013114 (1979)","journal-title":"SIAM J. Comput."},{"key":"1142_CR84","unstructured":"Pemmaraju, S.V.: Exploring the Powers of Stacks and Queues via Graph Layouts. PhD thesis, Virginia Polytechnic Institute and State University at Blacksburg, Virginia, (1992)"},{"issue":"1","key":"1142_CR85","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1093\/comjnl\/bxw064","volume":"60","author":"A Rextin","year":"2017","unstructured":"Rextin, A., Healy, P.: Dynamic upward planarity testing of single source embedded digraphs. Comput. J. 60(1), 45\u201359 (2017)","journal-title":"Comput. J."},{"key":"1142_CR86","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. x. obstructions to tree-decomposition. J. Comb. Theory, Ser. B, 52(2):153\u2013190,( 1991)","DOI":"10.1016\/0095-8956(91)90061-N"},{"issue":"2","key":"1142_CR87","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"PD Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"1142_CR88","doi-asserted-by":"crossref","unstructured":"Syslo, M.M.: Bounds to the page number of partially ordered sets. In: Nagl, M., (ed.) Graph-Theoretic Concepts in Computer Science, WG \u201989, volume 411 of LNCS, pp. 181\u2013195. Springer, (1989)","DOI":"10.1007\/3-540-52292-1_13"},{"key":"1142_CR89","doi-asserted-by":"crossref","unstructured":"Unger, W.: On the $$k$$-colouring of circle-graphs. In: Cori, R., Wirsing, M., (eds.) STACS 88, volume 294 of LNCS, pp. 61\u201372. Springer, (1988)","DOI":"10.1007\/BFb0035832"},{"key":"1142_CR90","doi-asserted-by":"crossref","unstructured":"Unger, W.: The complexity of colouring circle graphs (extended abstract). In: Finkel,A., Jantzen, M., (eds.) STACS 92, volume 577 of LNCS, pp. 389\u2013400. Springer, (1992)","DOI":"10.1007\/3-540-55210-3_199"},{"key":"1142_CR91","unstructured":"Wigderson, A.: The complexity of the Hamiltonian circuit problem for maximal planar graphs. Technical report, 298, EECS Department, Princeton University, (1982)"},{"key":"1142_CR92","doi-asserted-by":"crossref","unstructured":"Wood, D.R.: Bounded degree book embeddings and three-dimensional orthogonal graph drawing. In: Graph Drawing, volume 2265 of LNCS, pp. 312\u2013327. Springer, (2001)","DOI":"10.1007\/3-540-45848-4_25"},{"issue":"1","key":"1142_CR93","doi-asserted-by":"crossref","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)","journal-title":"J. Comput. Syst. Sci."},{"key":"1142_CR94","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Planar graphs that need four pages. J. Comb. Theory, Ser. B, 145:241\u2013263, (2020)","DOI":"10.1016\/j.jctb.2020.05.008"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01142-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01142-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01142-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,10]],"date-time":"2023-11-10T13:03:46Z","timestamp":1699621426000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01142-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,14]]},"references-count":94,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1142"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01142-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,7,14]]},"assertion":[{"value":"26 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}