{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:54Z","timestamp":1740109314594,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,5,9]],"date-time":"2022-05-09T00:00:00Z","timestamp":1652054400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,9]],"date-time":"2022-05-09T00:00:00Z","timestamp":1652054400000},"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":["20174LF3T8"],"award-info":[{"award-number":["20174LF3T8"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study universal sets of slopes for computing upward planar drawings of planar <jats:italic>st<\/jats:italic>-graphs. We first consider a subfamily of planar <jats:italic>st<\/jats:italic>-graphs, called bitonic <jats:italic>st<\/jats:italic>-graphs. We prove that every set <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {S}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>S<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varDelta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0394<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> slopes containing the horizontal slope is <jats:italic>universal<\/jats:italic> for 1-bend upward planar drawings of bitonic <jats:italic>st<\/jats:italic>-graphs with maximum vertex degree <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varDelta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0394<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, i.e., every such digraph admits a 1-bend upward planar drawing whose edge segments use only slopes in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {S}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>S<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This result is worst-case optimal in terms of number of slopes, and, for a suitable choice of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {S}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>S<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, it gives rise to drawings with worst-case optimal angular resolution. We then prove that every such set <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {S}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>S<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be used to construct 2-bend upward planar drawings of <jats:italic>n<\/jats:italic>-vertex planar <jats:italic>st<\/jats:italic>-graphs with at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$4n-9$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>4<\/mml:mn>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>9<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bends in total.<\/jats:p>","DOI":"10.1007\/s00453-022-00975-3","type":"journal-article","created":{"date-parts":[[2022,5,9]],"date-time":"2022-05-09T15:03:36Z","timestamp":1652108616000},"page":"2556-2580","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Universal Slope Sets for Upward Planar Drawings"],"prefix":"10.1007","volume":"84","author":[{"given":"Michael A.","family":"Bekos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emilio","family":"Di Giacomo","sequence":"additional","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0543-8912","authenticated-orcid":false,"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,9]]},"reference":[{"issue":"6","key":"975_CR1","doi-asserted-by":"publisher","first-page":"2527","DOI":"10.1007\/s00453-018-00542-9","volume":"81","author":"P Angelini","year":"2019","unstructured":"Angelini, P., Bekos, M.A., Liotta, G., Montecchiani, F.: Universal slope sets for 1-bend planar drawings. Algorithmica 81(6), 2527\u20132556 (2019). https:\/\/doi.org\/10.1007\/s00453-018-00542-9","journal-title":"Algorithmica"},{"issue":"2","key":"975_CR2","doi-asserted-by":"publisher","first-page":"657","DOI":"10.7155\/jgaa.00369","volume":"19","author":"MA Bekos","year":"2015","unstructured":"Bekos, M.A., Gronemann, M., Kaufmann, M., Krug, R.: Planar octilinear drawings with one bend per edge. J. Graph Algorithms Appl. 19(2), 657\u2013680 (2015). https:\/\/doi.org\/10.7155\/jgaa.00369","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"975_CR3","doi-asserted-by":"publisher","first-page":"709","DOI":"10.7155\/jgaa.00436","volume":"21","author":"MA Bekos","year":"2017","unstructured":"Bekos, M.A., Kaufmann, M., Krug, R.: On the total number of bends for planar octilinear drawings. J. Graph Algorithms Appl. 21(4), 709\u2013730 (2017). https:\/\/doi.org\/10.7155\/jgaa.00436","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"975_CR4","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1137\/S0097539794279626","journal-title":"SIAM J. Comput."},{"issue":"3","key":"975_CR5","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). https:\/\/doi.org\/10.1016\/S0925-7721(97)00026-6","journal-title":"Comput. Geom."},{"key":"975_CR6","doi-asserted-by":"publisher","first-page":"89","DOI":"10.7155\/jgaa.00083","volume":"8","author":"HL Bodlaender","year":"2004","unstructured":"Bodlaender, H.L., Tel, G.: A note on rectilinearity and angular resolution. J. Graph Algorithms Appl. 8, 89\u201394 (2004). https:\/\/doi.org\/10.7155\/jgaa.00083","journal-title":"J. Graph Algorithms Appl."},{"key":"975_CR7","doi-asserted-by":"publisher","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.) Graph Drawing and Network Visualization, GD 2017. LNCS, vol. 10692, pp. 465\u2013478. Springer, Berlin (2017). https:\/\/doi.org\/10.1007\/978-3-319-73915-1_36","DOI":"10.1007\/978-3-319-73915-1_36"},{"key":"975_CR8","doi-asserted-by":"crossref","unstructured":"Chaplick, S., Da Lozzo, G., Di Giacomo, E., Liotta, G., Montecchiani, F.: Planar drawings with few slopes of Halin graphs and nested pseudotrees. In: Algorithms and Data Structures, WADS 2021. LNCS, vol. 12808, pp. 271\u2013285. Springer, Berlin (2021)","DOI":"10.1007\/978-3-030-83508-8_20"},{"key":"975_CR9","doi-asserted-by":"crossref","unstructured":"Chimani, M., Zeranski, R.: Upward planarity testing in practice: SAT formulations and comparative study. ACM J. Exp. Algorithmics 20:1.2:1.1\u20131.2:1.27 (2015). https:\/\/doi.org\/10.1145\/2699875","DOI":"10.1145\/2699875"},{"issue":"4","key":"975_CR10","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0020-0190(95)00020-D","volume":"54","author":"M Chrobak","year":"1995","unstructured":"Chrobak, M., Payne, T.H.: A linear-time algorithm for drawing a planar graph on a grid. Inf. Process. Lett. 54(4), 241\u2013246 (1995). https:\/\/doi.org\/10.1016\/0020-0190(95)00020-D","journal-title":"Inf. Process. Lett."},{"key":"975_CR11","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"issue":"1","key":"975_CR12","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0097-3165(91)90025-C","volume":"56","author":"J Czyzowicz","year":"1991","unstructured":"Czyzowicz, J.: Lattice diagrams with few slopes. J. Comb. Theory Ser. A 56(1), 96\u2013108 (1991). https:\/\/doi.org\/10.1016\/0097-3165(91)90025-C","journal-title":"J. Comb. Theory Ser. A"},{"issue":"3","key":"975_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0012-365X(90)90201-R","volume":"82","author":"J Czyzowicz","year":"1990","unstructured":"Czyzowicz, J., Pelc, A., Rival, I.: Drawing orders with few slopes. Discrete Math. 82(3), 233\u2013250 (1990). https:\/\/doi.org\/10.1016\/0012-365X(90)90201-R","journal-title":"Discrete Math."},{"issue":"1","key":"975_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H de Fraysseix","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41\u201351 (1990). https:\/\/doi.org\/10.1007\/BF02122694","journal-title":"Combinatorica"},{"issue":"3","key":"975_CR15","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/j.comgeo.2013.10.002","volume":"47","author":"D Delling","year":"2014","unstructured":"Delling, D., Gemsa, A., N\u00f6llenburg, M., Pajor, T., Rutter, I.: On $$d$$-regular schematization of embedded paths. Comput. Geom. 47(3), 381\u2013406 (2014). https:\/\/doi.org\/10.1016\/j.comgeo.2013.10.002","journal-title":"Comput. Geom."},{"key":"975_CR16","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/0304-3975(88)90123-5","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"975_CR17","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":"975_CR18","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":"975_CR19","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)","journal-title":"Comput. Geom."},{"key":"975_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27848-8_653-1","volume-title":"Encyclopedia of Algorithms","author":"W Didimo","year":"2015","unstructured":"Didimo, W.: Upward graph drawing. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms. Springer, Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-642-27848-8_653-1"},{"issue":"3","key":"975_CR21","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/j.comgeo.2006.08.002","volume":"38","author":"V Dujmovi\u0107","year":"2007","unstructured":"Dujmovi\u0107, 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.08.002","journal-title":"Comput. Geom."},{"issue":"3","key":"975_CR22","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."},{"key":"975_CR23","volume-title":"Handbook on Graph Drawing and Visualization","author":"C Duncan","year":"2013","unstructured":"Duncan, C., Goodrich, M.T.: Planar orthogonal and polyline drawing algorithms. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization. Chapman and Hall\/CRC, London (2013)"},{"key":"975_CR24","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-319-03841-4_13","volume-title":"Graph Drawing, GD 2013, LNCS","author":"S Durocher","year":"2013","unstructured":"Durocher, S., Mondal, D.: On balanced +-contact representations. In: Wismath, S.K., Wolff, A. (eds.) Graph Drawing, GD 2013, LNCS, vol. 8242, pp. 143\u2013154. Springer, Berlin (2013). https:\/\/doi.org\/10.1007\/978-3-319-03841-4_13"},{"issue":"2","key":"975_CR25","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). https:\/\/doi.org\/10.1137\/S0097539794277123","journal-title":"SIAM J. Comput."},{"key":"975_CR26","doi-asserted-by":"crossref","unstructured":"Gronemann, M.: Bitonic $$st$$-orderings of biconnected planar graphs. In: Graph Drawing, GD 2014, LNCS, vol. 8871, pp. 162\u2013173. Springer, Berlin (2014)","DOI":"10.1007\/978-3-662-45803-7_14"},{"key":"975_CR27","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-319-50106-2_18","volume-title":"Graph Drawing and Network Visualization, GD 2016, LNCS","author":"M Gronemann","year":"2016","unstructured":"Gronemann, M.: Bitonic $$st$$-orderings for upward planar graphs. In: Hu, Y., N\u00f6llenburg, M. (eds.) Graph Drawing and Network Visualization, GD 2016, LNCS, vol. 9801, pp. 222\u2013235. Springer, Berlin (2016). https:\/\/doi.org\/10.1007\/978-3-319-50106-2_18"},{"key":"975_CR28","volume-title":"Graph Theory","author":"F Harary","year":"1972","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading (1972)"},{"key":"975_CR29","volume-title":"Handbook on Graph Drawing and Visualization","author":"P Healy","year":"2013","unstructured":"Healy, P., Nikolov, N.S.: Hierarchical drawing algorithms. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization. Chapman and Hall\/CRC, London (2013)"},{"issue":"3","key":"975_CR30","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/j.jvlc.2005.09.001","volume":"17","author":"S Hong","year":"2006","unstructured":"Hong, S., Merrick, D., do Nascimento, H.A.D.: Automatic visualisation of metro maps. J. Vis. Lang. Comput. 17(3), 203\u2013224 (2006). https:\/\/doi.org\/10.1016\/j.jvlc.2005.09.001","journal-title":"J. Vis. Lang. Comput."},{"issue":"4","key":"975_CR31","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1007\/s00373-012-1157-z","volume":"29","author":"V Jel\u00ednek","year":"2013","unstructured":"Jel\u00ednek, V., Jel\u00ednkov\u00e1, E., Kratochv\u00edl, J., Lidick\u00fd, B., Tesar, M., Vyskocil, T.: The planar slope number of planar partial 3-trees of bounded degree. Graphs Comb. 29(4), 981\u20131005 (2013). https:\/\/doi.org\/10.1007\/s00373-012-1157-z","journal-title":"Graphs Comb."},{"issue":"2\u20133","key":"975_CR32","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0012-365X(87)90008-2","volume":"63","author":"D Kelly","year":"1987","unstructured":"Kelly, D.: Fundamentals of planar ordered sets. Discrete Math. 63(2\u20133), 197\u2013216 (1987). https:\/\/doi.org\/10.1016\/0012-365X(87)90008-2","journal-title":"Discrete Math."},{"issue":"2","key":"975_CR33","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. Discrete Math. 27(2), 1171\u20131183 (2013). https:\/\/doi.org\/10.1137\/100815001","journal-title":"SIAM J. Discrete Math."},{"key":"975_CR34","doi-asserted-by":"crossref","unstructured":"Klawitter, J., Mchedlidze, T.: Upward planar drawings with two slopes. CoRR (2021). arxiv.org\/abs\/2106.02839","DOI":"10.1007\/978-3-030-92931-2_11"},{"key":"975_CR35","doi-asserted-by":"publisher","unstructured":"Klawitter, J., Zink, J.: Upward planar drawings with three and more slopes, vol. 12868, pp. 149\u2013165 (2021). https:\/\/doi.org\/10.1007\/978-3-030-92931-2_11","DOI":"10.1007\/978-3-030-92931-2_11"},{"key":"975_CR36","doi-asserted-by":"publisher","unstructured":"Knauer, K., Walczak, B.: Graph drawings with one bend and few slopes. In: Latin American Theoretical INformatics, LATIN 2016, LNCS, vol. 9644, pp. 549\u2013561. Springer, Berlin (2016). https:\/\/doi.org\/10.1007\/978-3-662-49529-2_41","DOI":"10.1007\/978-3-662-49529-2_41"},{"issue":"5","key":"975_CR37","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":"975_CR38","doi-asserted-by":"publisher","unstructured":"Leiserson, C.E.: Area-efficient graph layouts (for VLSI). In: Symposium on Foundations of Computer Science, FOCS 1980, pp. 270\u2013281. IEEE (1980). https:\/\/doi.org\/10.1109\/SFCS.1980.13","DOI":"10.1109\/SFCS.1980.13"},{"key":"975_CR39","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/978-3-319-03841-4_36","volume-title":"Graph Drawing and Network Visualization, GD 2013, LNCS","author":"W Lenhart","year":"2013","unstructured":"Lenhart, W., Liotta, G., Mondal, D., Nishat, R.I.: Planar and plane slope number of partial 2-trees. In: Wismath, S.K., Wolff, A. (eds.) Graph Drawing and Network Visualization, GD 2013, LNCS, vol. 8242, pp. 412\u2013423. Springer, Berlin (2013). https:\/\/doi.org\/10.1007\/978-3-319-03841-4_36"},{"key":"975_CR40","unstructured":"N\u00f6llenburg, M.: Automated drawings of metro maps. Technical Report 2005-25, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe (2005)"},{"issue":"5","key":"975_CR41","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1109\/TVCG.2010.81","volume":"17","author":"M N\u00f6llenburg","year":"2011","unstructured":"N\u00f6llenburg, M., Wolff, A.: Drawing and labeling high-quality metro maps by mixed-integer programming. IEEE Trans. Vis. Comput. Graph. 17(5), 626\u2013641 (2011). https:\/\/doi.org\/10.1109\/TVCG.2010.81","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"975_CR42","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Johnson, D.S. (ed.) Symposium on Discrete Algorithms, SODA 1990, pp. 138\u2013148. SIAM (1990)"},{"issue":"1","key":"975_CR43","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1109\/TVCG.2010.24","volume":"17","author":"JM Stott","year":"2011","unstructured":"Stott, J.M., Rodgers, P., Martinez-Ovando, J.C., Walker, S.G.: Automatic metro map layout using multicriteria optimization. IEEE Trans. Vis. Comput. Graph. 17(1), 101\u2013114 (2011). https:\/\/doi.org\/10.1109\/TVCG.2010.24","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"3","key":"975_CR44","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."},{"issue":"2","key":"975_CR45","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"30","author":"LG Valiant","year":"1981","unstructured":"Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Trans. Comput. 30(2), 135\u2013140 (1981). https:\/\/doi.org\/10.1109\/TC.1981.6312176","journal-title":"IEEE Trans. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00975-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00975-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00975-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,26]],"date-time":"2022-08-26T14:06:11Z","timestamp":1661522771000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00975-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,9]]},"references-count":45,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["975"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00975-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,5,9]]},"assertion":[{"value":"30 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2022","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding note","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}