{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:09Z","timestamp":1771036329313,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2024,8,4]],"date-time":"2024-08-04T00:00:00Z","timestamp":1722729600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,4]],"date-time":"2024-08-04T00:00:00Z","timestamp":1722729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN Proj. 2022ME9Z78"],"award-info":[{"award-number":["PRIN Proj. 2022ME9Z78"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN Proj. 2022TS4Y3N"],"award-info":[{"award-number":["PRIN Proj. 2022TS4Y3N"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN Proj. 2022TS4Y3N"],"award-info":[{"award-number":["PRIN Proj. 2022TS4Y3N"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN Proj. 2022ME9Z78"],"award-info":[{"award-number":["PRIN Proj. 2022ME9Z78"]}],"id":[{"id":"10.13039\/501100021856","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":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Computing planar orthogonal drawings with the minimum number of bends is one of the most studied topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia in SIAM J Comput 31(2):601\u2013625, 2001). From the parameterized complexity perspective, the problem is fixed-parameter tractable when parameterized by the sum of three parameters: the number <jats:italic>b<\/jats:italic> of bends, the number <jats:italic>k<\/jats:italic> of vertices of degree at most two, and the treewidth <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf{tw}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>tw<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the input graph (Di Giacomo et al. in J Comput Syst Sci 125:129\u2013148, 2022). We improve this last result by showing that the problem remains fixed-parameter tractable when parameterized only by <jats:inline-formula><jats:alternatives><jats:tex-math>$$b+k$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>b<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. As a consequence, rectilinear planarity testing lies in FPT\u00a0parameterized by the number of vertices of degree at most two. We also prove that our choice of parameters is minimal, as deciding if an orthogonal drawing with at most <jats:italic>b<\/jats:italic> bends exists is already NP-hard when <jats:italic>k<\/jats:italic> is zero (i.e., the problem is para-NP-hard parameterized in <jats:italic>k<\/jats:italic>); hence, there is neither an FPT nor an XP algorithm parameterized only by the parameter <jats:italic>k<\/jats:italic> (unless P\u00a0=\u00a0NP). In addition, we prove that the problem is W[1]-hard parameterized by <jats:inline-formula><jats:alternatives><jats:tex-math>$$k+\\textsf{tw}$$<\/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:mi>tw<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, complementing a recent result (Jansen et al. in Upward and orthogonal planarity are W[1]-hard parameterized by treewidth. CoRR, abs\/2309.01264, 2023; in: Bekos MA, Chimani M (eds) Graph Drawing and Network Visualization, vol 14466, Springer, Cham, pp 203\u2013217, 2023) that shows W[1]-hardness for the parameterization <jats:inline-formula><jats:alternatives><jats:tex-math>$$b+\\textsf{tw}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>b<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>tw<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. As a consequence, we are able to trace a clear parameterized tractability landscape for the bend-minimum orthogonal planarity problem with respect to the three parameters <jats:italic>b<\/jats:italic>, <jats:italic>k<\/jats:italic>, and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf{tw}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>tw<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00453-024-01260-1","type":"journal-article","created":{"date-parts":[[2024,8,4]],"date-time":"2024-08-04T13:02:00Z","timestamp":1722776520000},"page":"3231-3251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Parameterized Complexity of Bend-Minimum Orthogonal Planarity"],"prefix":"10.1007","volume":"86","author":[{"given":"Emilio","family":"Di Giacomo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Walter","family":"Didimo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Montecchiani","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":[[2024,8,4]]},"reference":[{"issue":"3","key":"1260_CR1","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0925-7721(97)00026-6","volume":"9","author":"TC Biedl","year":"1998","unstructured":"Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159\u2013180 (1998)","journal-title":"Comput. Geom."},{"key":"1260_CR2","unstructured":"Bodlaender, H.L., Groenland, C., Jacob, H., Pilipczuk, M., Pilipczuk, M.: On the complexity of problems on tree-structured graphs. In: Dell, H., Nederlof, J. (eds.), 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, LIPIcs, vol. 249, pp. 6:1\u20136:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"1260_CR3","unstructured":"Chaplick, S., Di Giacomo, E., Frati, F., Ganian, R., Raftopoulou, C.N., Simonov, K.: Parameterized algorithms for upward planarity. In: Goaoc, X., Kerber, M. (eds.), 38th International Symposium on Computational Geometry, SoCG 2022, June 7\u201310, 2022, Berlin, Germany, LIPIcs, vol. 224, pp. 26:1\u201326:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"issue":"3","key":"1260_CR4","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":"1260_CR5","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":"1260_CR6","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":"1260_CR7","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-031-49275-4_4","volume-title":"Graph Drawing and Network Visualization","author":"E Di Giacomo","year":"2023","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Montecchiani, F., Ortali, G.: On the parameterized complexity of bend-minimum orthogonal planarity. In: Bekos, M.A., Chimani, M. (eds.) Graph Drawing and Network Visualization, vol. 14466, pp. 53\u201365. Springer, Cham (2023)"},{"key":"1260_CR8","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."},{"issue":"4","key":"1260_CR9","doi-asserted-by":"publisher","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. Discret. Math. 23(4), 1842\u20131899 (2009)","journal-title":"SIAM J. Discret. Math."},{"key":"1260_CR10","doi-asserted-by":"crossref","unstructured":"Didimo,W., Kaufmann,M., Liotta,G., Ortali,G.: Rectilinear planarity of partial 2-trees. In: Angelini, P., von Hanxleden, R. (eds.) Graph Drawing and Network Visualization\u201430th International Symposium, GD 2022, LNCS, vol. 13764, 157\u2013172. Springer (2022)","DOI":"10.1007\/978-3-031-22203-0_12"},{"key":"1260_CR11","doi-asserted-by":"crossref","unstructured":"Didimo, W., Kaufmann, M., Liotta, G., Ortali, G.: Computing bend-minimum orthogonal drawings of plane series-parallel graphs in linear time. Algorithmica (2023)","DOI":"10.1007\/s00453-023-01110-6"},{"key":"1260_CR12","unstructured":"Didimo, W., Liotta, G.: Computing orthogonal drawings in a variable embedding setting. In: Chwa, K., Ibarra, O. H. (eds.) Algorithms and Computation, 9th International Symposium, ISAAC\u201998, Taejon, Korea, December 14\u201316, 1998, Proceedings, Lecture Notes in Computer Science, vol. 1533, pp. 79\u201388. Springer (1998)"},{"key":"1260_CR13","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.) SODA 2020, pp. 806\u2013825. SIAM (2020)","DOI":"10.1137\/1.9781611975994.49"},{"key":"1260_CR14","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":"1260_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2021.101854","volume":"103","author":"F Frati","year":"2022","unstructured":"Frati, F.: Planar rectilinear drawings of outerplanar graphs in linear time. Comput. Geom. 103, 101854 (2022)","journal-title":"Comput. Geom."},{"issue":"6","key":"1260_CR16","first-page":"82","volume":"11","author":"R Ganian","year":"2021","unstructured":"Ganian, R., Montecchiani, F., N\u00f6llenburg, M., Zehavi, M.: Parameterized complexity in graph drawing (Dagstuhl Seminar 21293). Dagstuhl Rep. 11(6), 82\u2013123 (2021)","journal-title":"Dagstuhl Rep."},{"key":"1260_CR17","doi-asserted-by":"crossref","unstructured":"Garg, A., Tamassia, R.: A new minimum cost flow algorithm with applications to graph drawing. In: North, S.C. (eds.) Graph Drawing, Symposium on Graph Drawing, GD\u201996, Berkeley, California, USA, September 18\u201320, Proceedings, Lecture Notes in Computer Science, vol. 1190, pp. 201\u2013216. Springer (1996)","DOI":"10.1007\/3-540-62495-3_49"},{"issue":"2","key":"1260_CR18","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":"1260_CR19","doi-asserted-by":"crossref","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Graph Drawing, 8th International Symposium, GD 2000, Colonial Williamsburg, VA, USA, September 20\u201323, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1984, pp. 77\u201390. Springer (2000)","DOI":"10.1007\/3-540-44541-2_8"},{"issue":"3","key":"1260_CR20","doi-asserted-by":"publisher","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":"1260_CR21","doi-asserted-by":"crossref","unstructured":"Jansen, B. M. P., Khazaliya, L., Kindermann, P., Liotta,P., Montecchiani, F., Simonov, K.: Upward and orthogonal planarity are W[1]-hard parameterized by treewidth. CoRR, abs\/2309.01264 (2023)","DOI":"10.1007\/978-3-031-49275-4_14"},{"key":"1260_CR22","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-031-49275-4_14","volume-title":"Graph Drawing and Network Visualization","author":"BMP Jansen","year":"2023","unstructured":"Jansen, B.M.P., Khazaliya, L., Kindermann, P., Liotta, G., Montecchiani, F., Simonov, K.: Upward and orthogonal planarity are W[1]-hard parameterized by treewidth. In: Bekos, M.A., Chimani, M. (eds.) Graph Drawing and Network Visualization, vol. 14466, pp. 203\u2013217. Springer, Cham (2023)"},{"issue":"4","key":"1260_CR23","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."},{"issue":"3","key":"1260_CR24","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."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01260-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01260-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01260-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T07:05:37Z","timestamp":1727679937000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01260-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,4]]},"references-count":24,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["1260"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01260-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,4]]},"assertion":[{"value":"12 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors of this paper declare that they have no conflict of interest as defined by Springer, or other interests that might be perceived to influence the results and\/or discussion reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}