{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T10:56:49Z","timestamp":1770461809771,"version":"3.49.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2023,3,11]],"date-time":"2023-03-11T00:00:00Z","timestamp":1678492800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,11]],"date-time":"2023-03-11T00:00:00Z","timestamp":1678492800000},"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"],"award-info":[{"award-number":["PRIN 20174LF3T8"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010607","name":"Universit\u00e0 degli Studi di Perugia","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100010607","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A <jats:italic>planar orthogonal drawing<\/jats:italic> of a planar 4-graph <jats:italic>G<\/jats:italic> (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of <jats:italic>G<\/jats:italic> to a distinct point of the plane and each edge of <jats:italic>G<\/jats:italic> to a polygonal chain consisting of horizontal and vertical segments. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a <jats:italic>plane<\/jats:italic> 4-graph with the minimum number of bends. The term \u201cplane\u201d indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper we positively answer the question above for the widely-studied class of series\u2013parallel graphs. Our linear-time algorithm is based on a characterization of the planar series\u2013parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take; the orthogonal spirality of a component measures how much that component is \u201crolled-up\u201d in an orthogonal drawing of the graph.<\/jats:p>","DOI":"10.1007\/s00453-023-01110-6","type":"journal-article","created":{"date-parts":[[2023,3,11]],"date-time":"2023-03-11T11:02:33Z","timestamp":1678532553000},"page":"2605-2666","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Computing Bend-Minimum Orthogonal Drawings of Plane Series\u2013Parallel Graphs in Linear Time"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4379-6059","authenticated-orcid":false,"given":"Walter","family":"Didimo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giacomo","family":"Ortali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,11]]},"reference":[{"key":"1110_CR1","doi-asserted-by":"crossref","unstructured":"Brandenburg, F., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Liotta, G., Mutzel, P.: Selected open problems in graph drawing. In: Graph Drawing, volume 2912 of Lecture Notes in Computer Science, pp. 515\u2013539. Springer, Berlin (2003)","DOI":"10.1007\/978-3-540-24595-7_55"},{"issue":"3","key":"1110_CR2","doi-asserted-by":"publisher","first-page":"635","DOI":"10.7155\/jgaa.00265","volume":"16","author":"S Cornelsen","year":"2012","unstructured":"Cornelsen, S., Karrenbauer, A.: Accelerated bend minimization. J. Graph Algorithms Appl. 16(3), 635\u2013650 (2012)","journal-title":"J. Graph Algorithms Appl."},{"key":"1110_CR3","volume-title":"Graph Drawing","author":"G Di Battista","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River (1999)"},{"key":"1110_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, Upper Saddle River (1999)"},{"issue":"6","key":"1110_CR5","doi-asserted-by":"publisher","first-page":"1764","DOI":"10.1137\/S0097539794262847","volume":"27","author":"G Di Battista","year":"1998","unstructured":"Di Battista, G., Liotta, G., Vargiu, F.: Spirality and optimal orthogonal drawings. SIAM J. Comput. 27(6), 1764\u20131811 (1998)","journal-title":"SIAM J. Comput."},{"key":"1110_CR6","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.jcss.2021.11.004","volume":"125","author":"E Di Giacomo","year":"2022","unstructured":"Di Giacomo, E., Liotta, G., Montecchiani, F.: Orthogonal planarity testing of bounded treewidth graphs. J. Comput. Syst. Sci. 125, 129\u2013148 (2022)","journal-title":"J. Comput. Syst. Sci."},{"key":"1110_CR7","unstructured":"Di Giacomo, E., Liotta, G., Tamassia, R.: Graph drawing. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn., chapter\u00a055, pp. 1451\u20131478. Chapman and Hall\/CRC, London (2017)"},{"key":"1110_CR8","doi-asserted-by":"crossref","unstructured":"Didimo, W., Kaufmann, M., Liotta, G., Ortali, G.: Rectilinear planarity testing of plane series-parallel graphs in linear time. In: Graph Drawing, volume 12590 of Lecture Notes in Computer Science, pp. 436\u2013449. Springer, Berlin (2020)","DOI":"10.1007\/978-3-030-68766-3_34"},{"key":"1110_CR9","doi-asserted-by":"crossref","unstructured":"Didimo, W., Liotta, G.: Computing orthogonal drawings in a variable embedding setting. In: ISAAC, volume 1533 of Lecture Notes in Computer Science, pp. 79\u201388. Springer, Berlin (1998)","DOI":"10.1007\/3-540-49381-6_10"},{"key":"1110_CR10","doi-asserted-by":"crossref","unstructured":"Didimo, W., Liotta, G., Ortali, G., Patrignani, M.: Optimal orthogonal drawings of planar 3-graphs in linear time. In: Chawla, S. (eds) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5\u20138, 2020, pp. 806\u2013825. SIAM (2020)","DOI":"10.1137\/1.9781611975994.49"},{"key":"1110_CR11","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.jcss.2018.08.003","volume":"99","author":"W Didimo","year":"2019","unstructured":"Didimo, W., Liotta, G., Patrignani, M.: HV-planarity: algorithms and complexity. J. Comput. Syst. Sci. 99, 72\u201390 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"1110_CR12","first-page":"223","volume-title":"Handbook on Graph Drawing and Visualization","author":"CA Duncan","year":"2013","unstructured":"Duncan, C.A., Goodrich, M.T.: Planar orthogonal and polyline drawing algorithms. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization, pp. 223\u2013246. Chapman and Hall\/CRC, London (2013)"},{"key":"1110_CR13","doi-asserted-by":"crossref","unstructured":"Garg, A., Liotta, G.: Almost bend-optimal planar orthogonal drawings of biconnected degree-3 planar graphs in quadratic time. In: Graph Drawing, volume 1731 of Lecture Notes in Computer Science, pp. 38\u201348. Springer, Berlin (1999)","DOI":"10.1007\/3-540-46648-7_4"},{"issue":"2","key":"1110_CR14","doi-asserted-by":"publisher","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":"1110_CR15","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., Wagner, D. (eds): Drawing Graphs, Methods and Models (the book grow out of a Dagstuhl Seminar, April 1999), volume 2025 of Lecture Notes in Computer Science. Springer, Berlin (2001)","DOI":"10.1007\/3-540-44969-8"},{"key":"1110_CR16","volume-title":"Planar Graphs: Theory and Algorithms","author":"T Nishizeki","year":"2008","unstructured":"Nishizeki, T., Chiba, N.: Planar Graphs: Theory and Algorithms. Dover Publications Inc., Mineola (2008)"},{"key":"1110_CR17","doi-asserted-by":"crossref","unstructured":"Nishizeki, T., Rahman, M.S.: Planar Graph Drawing, volume\u00a012 of Lecture Notes Series on Computing. World Scientific, Singapore (2004)","DOI":"10.1142\/5648"},{"issue":"4","key":"1110_CR18","doi-asserted-by":"publisher","first-page":"31","DOI":"10.7155\/jgaa.00017","volume":"3","author":"MS Rahman","year":"1999","unstructured":"Rahman, M.S., Nakano, S., Nishizeki, T.: A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs. J. Graph Algorithms Appl. 3(4), 31\u201362 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"1110_CR19","doi-asserted-by":"crossref","unstructured":"Rahman, M.S., Nishizeki, T.: Bend-minimum orthogonal drawings of plane 3-graphs. In: Kucera, L. (ed.) Graph-Theoretic Concepts in Computer Science, 28th International Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13\u201315, 2002, Revised Papers, volume 2573 of Lecture Notes in Computer Science, pp. 367\u2013378. Springer, Berlin (2002)","DOI":"10.1007\/3-540-36379-3_32"},{"issue":"3","key":"1110_CR20","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K Takamizawa","year":"1982","unstructured":"Takamizawa, K., Nishizeki, T., Saito, N.: Linear-time computability of combinatorial problems on series-parallel graphs. J. ACM 29(3), 623\u2013641 (1982)","journal-title":"J. ACM"},{"issue":"3","key":"1110_CR21","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R Tamassia","year":"1987","unstructured":"Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421\u2013444 (1987)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1110_CR22","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM J. Comput. 11(2), 298\u2013313 (1982)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1110_CR23","doi-asserted-by":"publisher","first-page":"1570","DOI":"10.1137\/060667621","volume":"22","author":"X Zhou","year":"2008","unstructured":"Zhou, X., Nishizeki, T.: Orthogonal drawings of series-parallel graphs with minimum bends. SIAM J. Discrete Math. 22(4), 1570\u20131604 (2008)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01110-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01110-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01110-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T15:03:36Z","timestamp":1695395016000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01110-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,11]]},"references-count":23,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1110"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01110-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,11]]},"assertion":[{"value":"27 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}