{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:42:26Z","timestamp":1770741746409,"version":"3.49.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T00:00:00Z","timestamp":1637280000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T00:00:00Z","timestamp":1637280000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Karlsruher Institut f\u00fcr Technologie (KIT)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce and study level-planar straight-line drawings with a fixed number\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\lambda $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03bb<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of slopes. For proper level graphs (all edges connect vertices of adjacent levels), we give an\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n \\log ^2 n \/ \\log \\log n)$$<\/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>n<\/mml:mi>\n                    <mml:msup>\n                      <mml:mo>log<\/mml:mo>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithm that either finds such a drawing or determines that no such drawing exists. Moreover, we consider the partial drawing extension problem, where we seek to extend an immutable drawing of a subgraph to a drawing of the whole graph, and the simultaneous drawing problem, which asks about the existence of drawings of two graphs whose restrictions to their shared subgraph coincide. We present\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^{4\/3} \\log n)$$<\/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:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mn>4<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>3<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time and\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\lambda n^{10\/3} \\log n)$$<\/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>\u03bb<\/mml:mi>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mn>10<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>3<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithms for these respective problems on proper level-planar graphs. We complement these positive results by showing that testing whether non-proper level graphs admit level-planar drawings with\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\lambda $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03bb<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> slopes is -hard even in restricted cases.<\/jats:p>","DOI":"10.1007\/s00453-021-00884-x","type":"journal-article","created":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T09:25:47Z","timestamp":1637313947000},"page":"176-196","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Level-Planar Drawings with Few Slopes"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8867-2244","authenticated-orcid":false,"given":"Guido","family":"Br\u00fcckner","sequence":"first","affiliation":[]},{"given":"Nadine","family":"Krisam","sequence":"additional","affiliation":[]},{"given":"Tamara","family":"Mchedlidze","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,19]]},"reference":[{"key":"884_CR1","unstructured":"FAUSTEDITION. http:\/\/www.faustedition.net\/macrogenesis\/dag"},{"key":"884_CR2","doi-asserted-by":"publisher","unstructured":"Angelini, P., Chaplick, S., Cornelsen, S., Da Lozzo, G., Di Battista, G., Eades, P., Kindermann, P., Kratochv\u00edl, J., Lipp, F., Rutter, I.: Simultaneous orthogonal planarity. In: Y.\u00a0Hu, M.\u00a0N\u00f6llenburg (eds.) Graph Drawing and Network Visualization\u201424th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers, Lecture Notes in Computer Science, vol. 9801, pp. 532\u2013545. Springer (2016). https:\/\/doi.org\/10.1007\/978-3-319-50106-2_41","DOI":"10.1007\/978-3-319-50106-2_41"},{"key":"884_CR3","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/j.tcs.2019.11.024","volume":"804","author":"P Angelini","year":"2020","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Beyond level planarity: Cyclic, torus, and simultaneous level planarity. Theor. Comput. Sci. 804, 161\u2013170 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2019.11.024","journal-title":"Theor. Comput. Sci."},{"key":"884_CR4","doi-asserted-by":"publisher","unstructured":"Bar\u00e1t, J., Matousek, J., Wood, D.R.: Bounded-degree graphs have arbitrarily large geometric thickness. Electron. J. Comb. 13(1) (2006). https:\/\/doi.org\/10.37236\/1029","DOI":"10.37236\/1029"},{"key":"884_CR5","doi-asserted-by":"publisher","unstructured":"Bekos, M.A., Di Giacomo, E., Didimo, W., Liotta, G., Montecchiani, F.: Universal slope sets for upward planar drawings. In: T.C. Biedl, A.\u00a0Kerren (eds.) Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, Proceedings, Lecture Notes in Computer Science, vol. 11282, pp. 77\u201391. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-030-04414-5_6","DOI":"10.1007\/978-3-030-04414-5_6"},{"key":"884_CR6","unstructured":"Bl\u00e4sius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: R.\u00a0Tamassia (ed.) Handbook on Graph Drawing and Visualization, pp. 349\u2013381. Chapman and Hall\/CRC (2013)"},{"issue":"3","key":"884_CR7","doi-asserted-by":"publisher","first-page":"33:1","DOI":"10.1145\/2838736","volume":"12","author":"T Bl\u00e4sius","year":"2016","unstructured":"Bl\u00e4sius, T., Rutter, I., Wagner, D.: Optimal orthogonal graph drawing with convex bend costs. ACM Trans. Algorith. 12(3), 33:1-33:32 (2016). https:\/\/doi.org\/10.1145\/2838736","journal-title":"ACM Trans. Algorith."},{"issue":"4","key":"884_CR8","doi-asserted-by":"publisher","first-page":"1280","DOI":"10.1137\/15M1042929","volume":"46","author":"G Borradaile","year":"2017","unstructured":"Borradaile, G., Klein, P.N., Mozes, S., Nussbaum, Y., Wulff-Nilsen, C.: Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. SIAM J. Comput. 46(4), 1280\u20131303 (2017). https:\/\/doi.org\/10.1137\/15M1042929","journal-title":"SIAM J. Comput."},{"key":"884_CR9","doi-asserted-by":"publisher","unstructured":"Br\u00fcckner, G., Krisam, N., Mchedlidze, T.: Level-planar drawings with few slopes. In: D.\u00a0Archambault, C.D. T\u00f3th (eds.) Graph Drawing and Network Visualization\u201427th International Symposium, GD 2019, Prague, Czech Republic, September 17-20, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11904, pp. 559\u2013572. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-35802-0_42","DOI":"10.1007\/978-3-030-35802-0_42"},{"key":"884_CR10","doi-asserted-by":"publisher","unstructured":"Br\u00fcckner, G., Rutter, I.: Partial and constrained level planarity. In: P.N. Klein (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 2000\u20132011. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.130","DOI":"10.1137\/1.9781611974782.130"},{"key":"884_CR11","doi-asserted-by":"publisher","unstructured":"Br\u00fcckner, G., Rutter, I.: An SPQR-tree-like embedding representation for level planarity. In: Y.\u00a0Cao, S.W. Cheng, M.\u00a0Li (eds.) 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), LIPIcs, vol. 181, pp. 8:1\u20138:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2020.8","DOI":"10.4230\/LIPIcs.ISAAC.2020.8"},{"key":"884_CR12","doi-asserted-by":"publisher","unstructured":"de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(3), 187\u2013206 (2012). https:\/\/doi.org\/10.1142\/S0218195912500045. http:\/\/www.worldscinet.com\/doi\/abs\/10.1142\/S0218195912500045","DOI":"10.1142\/S0218195912500045"},{"issue":"2","key":"884_CR13","doi-asserted-by":"publisher","first-page":"707","DOI":"10.7155\/jgaa.00376","volume":"19","author":"E Di Giacomo","year":"2015","unstructured":"Di Giacomo, E., Liotta, G., Montecchiani, F.: Drawing outer 1-planar graphs with few slopes. J. Graph Algorithms Appl. 19(2), 707\u2013741 (2015). https:\/\/doi.org\/10.7155\/jgaa.00376","journal-title":"J. Graph Algorithms Appl."},{"key":"884_CR14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2017.12.004","volume":"714","author":"E Di Giacomo","year":"2018","unstructured":"Di Giacomo, E., Liotta, G., Montecchiani, F.: Drawing subcubic planar graphs with four slopes and optimal angular resolution. Theor. Comput. Sci. 714, 51\u201373 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2017.12.004","journal-title":"Theor. Comput. Sci."},{"key":"884_CR15","doi-asserted-by":"publisher","first-page":"101628","DOI":"10.1016\/j.comgeo.2020.101628","volume":"90","author":"E Di Giacomo","year":"2020","unstructured":"Di Giacomo, E., Liotta, G., Montecchiani, F.: 1-bend upward planar slope number of SP-digraphs. Comput. Geom. 90, 101628 (2020). https:\/\/doi.org\/10.1016\/j.comgeo.2020.101628","journal-title":"Comput. Geom."},{"issue":"3","key":"884_CR16","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/j.comgeo.2006.09.002","volume":"38","author":"V Dujmovic","year":"2007","unstructured":"Dujmovic, V., Eppstein, D., Suderman, M., Wood, D.R.: Drawings of planar graphs with few slopes and segments. Comput. Geom. 38(3), 194\u2013212 (2007). https:\/\/doi.org\/10.1016\/j.comgeo.2006.09.002","journal-title":"Comput. Geom."},{"issue":"3","key":"884_CR17","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.comgeo.2006.08.002","volume":"38","author":"V Dujmovic","year":"2007","unstructured":"Dujmovic, V., Suderman, M., Wood, D.R.: Graph drawings with few slopes. Comput. Geom. 38(3), 181\u2013193 (2007). https:\/\/doi.org\/10.1016\/j.comgeo.2006.08.002","journal-title":"Comput. Geom."},{"issue":"4","key":"884_CR18","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S Even","year":"1976","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5(4), 691\u2013703 (1976). https:\/\/doi.org\/10.1137\/0205048","journal-title":"SIAM J. Comput."},{"issue":"5","key":"884_CR19","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1016\/j.jcss.2005.05.007","volume":"72","author":"J Fakcharoenphol","year":"2006","unstructured":"Fakcharoenphol, J., Rao, S.: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5), 868\u2013889 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2005.05.007","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"884_CR20","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0020-0190(81)90120-4","volume":"13","author":"R Hassin","year":"1981","unstructured":"Hassin, R.: Maximum flow in $$(s, t)$$ planar networks. Inf. Process. Lett. 13(3), 107 (1981). https:\/\/doi.org\/10.1016\/0020-0190(81)90120-4","journal-title":"Inf. Process. Lett."},{"key":"884_CR21","unstructured":"Healy, P., Nikolov, N.S.: Hierarchical drawing algorithms. In: R.\u00a0Tamassia (ed.) Handbook on Graph Drawing and Visualization, pp. 409\u2013453. Chapman and Hall\/CRC (2013)"},{"issue":"1","key":"884_CR22","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M Henzinger","year":"1997","unstructured":"Henzinger, M., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55(1), 3\u201323 (1997). https:\/\/doi.org\/10.1006\/jcss.1997.1493","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"884_CR23","doi-asserted-by":"publisher","first-page":"183","DOI":"10.7155\/jgaa.00411","volume":"21","author":"U Hoffmann","year":"2017","unstructured":"Hoffmann, U.: On the complexity of the planar slope number problem. J. Graph Algorithms Appl. 21(2), 183\u2013193 (2017). https:\/\/doi.org\/10.7155\/jgaa.00411","journal-title":"J. Graph Algorithms Appl."},{"key":"884_CR24","volume-title":"Integer Programming and Network Flows","author":"TC Hu","year":"1969","unstructured":"Hu, T.C.: Integer Programming and Network Flows. Addison-Wesley, Reading, MA (1969)"},{"issue":"2","key":"884_CR25","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0208012","volume":"8","author":"A Itai","year":"1979","unstructured":"Itai, A., Shiloach, Y.: Maximum flow in planar networks. SIAM J. Comput. 8(2), 135\u2013150 (1979). https:\/\/doi.org\/10.1137\/0208012","journal-title":"SIAM J. Comput."},{"key":"884_CR26","doi-asserted-by":"publisher","unstructured":"J\u00e4nicke, S., Ge\u00dfner, A., Franzini, G., Terras, M., Mahony, S., Scheuermann, G.: Traviz: A visualization for variant graphs. Digit. Scholarsh. Humanit. 30(Suppl-1), i83\u2013i99 (2015). https:\/\/doi.org\/10.1093\/llc\/fqv049","DOI":"10.1093\/llc\/fqv049"},{"issue":"2","key":"884_CR27","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1137\/100815001","volume":"27","author":"B Keszegh","year":"2013","unstructured":"Keszegh, B., Pach, J., P\u00e1lv\u00f6lgyi, D.: Drawing planar graphs of bounded degree with few slopes. SIAM J. Discret. Math. 27(2), 1171\u20131183 (2013). https:\/\/doi.org\/10.1137\/100815001","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"884_CR28","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.comgeo.2007.05.003","volume":"40","author":"B Keszegh","year":"2008","unstructured":"Keszegh, B., Pach, J., P\u00e1lv\u00f6lgyi, D., T\u00f3th, G.: Drawing cubic graphs with at most five slopes. Comput. Geom. 40(2), 138\u2013147 (2008). https:\/\/doi.org\/10.1016\/j.comgeo.2007.05.003","journal-title":"Comput. Geom."},{"issue":"3","key":"884_CR29","doi-asserted-by":"publisher","first-page":"501","DOI":"10.7155\/jgaa.00474","volume":"22","author":"P Kindermann","year":"2018","unstructured":"Kindermann, P., Meulemans, W., Schulz, A.: Experimental analysis of the accessibility of drawings with few segments. J. Graph Algorithms Appl. 22(3), 501\u2013518 (2018). https:\/\/doi.org\/10.7155\/jgaa.00474","journal-title":"J. Graph Algorithms Appl."},{"key":"884_CR30","unstructured":"Kleinberg, J.M., Tardos, \u00c9.: Algorithm design. Addison-Wesley (2006)"},{"issue":"5","key":"884_CR31","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1016\/j.comgeo.2014.01.003","volume":"47","author":"KB Knauer","year":"2014","unstructured":"Knauer, K.B., Micek, P., Walczak, B.: Outerplanar graph drawings with few slopes. Comput. Geom. 47(5), 614\u2013624 (2014). https:\/\/doi.org\/10.1016\/j.comgeo.2014.01.003","journal-title":"Comput. Geom."},{"key":"884_CR32","doi-asserted-by":"publisher","unstructured":"Lenhart, W., Liotta, G., Mondal, D., Nishat, R.I.: Planar and plane slope number of partial 2-trees. In: S.K. Wismath, A.\u00a0Wolff (eds.) Graph Drawing - 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8242, pp. 412\u2013423. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-319-03841-4_36","DOI":"10.1007\/978-3-319-03841-4_36"},{"issue":"1","key":"884_CR33","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s00453-015-0018-6","volume":"76","author":"T Mchedlidze","year":"2016","unstructured":"Mchedlidze, T., N\u00f6llenburg, M., Rutter, I.: Extending convex partial drawings of graphs. Algorithmica 76(1), 47\u201367 (2016). https:\/\/doi.org\/10.1007\/s00453-015-0018-6","journal-title":"Algorithmica"},{"issue":"4","key":"884_CR34","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.orl.2009.03.006","volume":"37","author":"CA Meyers","year":"2009","unstructured":"Meyers, C.A., Schulz, A.S.: Integer equal flows. Oper. Res. Lett. 37(4), 245\u2013249 (2009). https:\/\/doi.org\/10.1016\/j.orl.2009.03.006","journal-title":"Oper. Res. Lett."},{"key":"884_CR35","doi-asserted-by":"publisher","unstructured":"Mozes, S., Wulff-Nilsen, C.: Shortest paths in planar graphs with real lengths in $$o(n \\log ^2 n \/ \\log \\log n)$$ time. In: M.\u00a0de Berg, U.\u00a0Meyer (eds.) Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II, Lecture Notes in Computer Science, vol. 6347, pp. 206\u2013217. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-15781-3_18","DOI":"10.1007\/978-3-642-15781-3_18"},{"key":"884_CR36","doi-asserted-by":"publisher","unstructured":"Nickel, S., N\u00f6llenburg, M.: Towards data-driven multilinear metro maps. In: A.\u00a0Pietarinen, P.\u00a0Chapman, L.\u00a0Bosveld-de Smet, V.\u00a0Giardino, J.E. Corter, S.\u00a0Linker (eds.) Diagrammatic Representation and Inference - 11th International Conference, Diagrams 2020, Tallinn, Estonia, August 24-28, 2020, Proceedings, Lecture Notes in Computer Science, vol. 12169, pp. 153\u2013161. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-54249-8_12","DOI":"10.1007\/978-3-030-54249-8_12"},{"key":"884_CR37","unstructured":"N\u00f6llenburg, M.: A survey on automated metro map layout methods. In: Schematic Mapping Workshop. Essex, UK (2014)"},{"key":"884_CR38","doi-asserted-by":"crossref","unstructured":"Pach, J., P\u00e1lv\u00f6lgyi, D.: Bounded-degree graphs can have arbitrarily large slope numbers. Electron. J. Comb. 13(1) (2006). http:\/\/www.combinatorics.org\/Volume_13\/Abstracts\/v13i1n1.html","DOI":"10.37236\/1139"},{"issue":"5","key":"884_CR39","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1142\/S0129054106004261","volume":"17","author":"M Patrignani","year":"2006","unstructured":"Patrignani, M.: On extending a partial straight-line drawing. Int. J. Found. Comput. Sci. 17(5), 1061\u20131070 (2006). https:\/\/doi.org\/10.1142\/S0129054106004261","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"5","key":"884_CR40","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1006\/jvlc.2002.0232","volume":"13","author":"HC Purchase","year":"2002","unstructured":"Purchase, H.C.: Metrics for graph drawing aesthetics. J. Vis. Lang. Comput. 13(5), 501\u2013516 (2002). https:\/\/doi.org\/10.1006\/jvlc.2002.0232","journal-title":"J. Vis. Lang. Comput."},{"issue":"4","key":"884_CR41","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1137\/0203021","volume":"3","author":"S Sahni","year":"1974","unstructured":"Sahni, S.: Computationally related problems. SIAM J. Comput. 3(4), 262\u2013279 (1974). https:\/\/doi.org\/10.1137\/0203021","journal-title":"SIAM J. Comput."},{"key":"884_CR42","doi-asserted-by":"publisher","unstructured":"Srinathan, K., Goundan, P.R., Kumar, M.V.N.A., Nandakumar, R., Rangan, C.P.: Theory of equal-flows in networks. In: O.H. Ibarra, L.\u00a0Zhang (eds.) Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2387, pp. 514\u2013524. Springer (2002). https:\/\/doi.org\/10.1007\/3-540-45655-4_55","DOI":"10.1007\/3-540-45655-4_55"},{"issue":"3","key":"884_CR43","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). https:\/\/doi.org\/10.1137\/0216030","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00884-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00884-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00884-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T14:08:46Z","timestamp":1643033326000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00884-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,19]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["884"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00884-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,19]]},"assertion":[{"value":"24 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}