{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T09:33:18Z","timestamp":1777627998921,"version":"3.51.4"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T00:00:00Z","timestamp":1546905600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00453-018-00542-9","type":"journal-article","created":{"date-parts":[[2019,1,9]],"date-time":"2019-01-09T02:20:37Z","timestamp":1547000437000},"page":"2527-2556","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Universal Slope Sets for 1-Bend Planar Drawings"],"prefix":"10.1007","volume":"81","author":[{"given":"Patrizio","family":"Angelini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Bekos","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":[[2019,1,8]]},"reference":[{"issue":"1","key":"542_CR1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.37236\/1029","volume":"13","author":"J Bar\u00e1t","year":"2006","unstructured":"Bar\u00e1t, J., Matou\u0161ek, J., Wood, D.R.: Bounded-degree graphs have arbitrarily large geometric thickness. Electron. J. Comb. 13(1), 3 (2006)","journal-title":"Electron. J. Comb."},{"issue":"2","key":"542_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)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"542_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)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"542_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)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"542_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)","journal-title":"Comput. Geom."},{"issue":"4","key":"542_CR6","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/s00453-012-9705-8","volume":"68","author":"T Bl\u00e4sius","year":"2014","unstructured":"Bl\u00e4sius, T., Krug, M., Rutter, I., Wagner, D.: Orthogonal graph drawing with flexibility constraints. Algorithmica 68(4), 859\u2013885 (2014)","journal-title":"Algorithmica"},{"key":"542_CR7","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.comgeo.2016.03.001","volume":"55","author":"T Bl\u00e4sius","year":"2016","unstructured":"Bl\u00e4sius, T., Lehmann, S., Rutter, I.: Orthogonal graph drawing with inflexible edges. Comput. Geom. 55, 26\u201340 (2016)","journal-title":"Comput. Geom."},{"key":"542_CR8","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)","journal-title":"J. Graph Algorithms Appl."},{"key":"542_CR9","doi-asserted-by":"crossref","unstructured":"Bonichon, N., Sa\u00ebc, B.\u00a0L., Mosbah, M.: Optimal area algorithm for planar polyline drawings. In: Kucera, L. (ed.) WG, vol. 2573 of LNCS, pp. 35\u201346. Springer, Berlin (2002)","DOI":"10.1007\/3-540-36379-3_4"},{"issue":"1","key":"542_CR10","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)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"3","key":"542_CR11","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)","journal-title":"Discrete Math."},{"issue":"2","key":"542_CR12","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF00383762","volume":"7","author":"J Czyzowicz","year":"1990","unstructured":"Czyzowicz, J., Pelc, A., Rival, I., Urrutia, J.: Crooked diagrams with few slopes. Order 7(2), 133\u2013143 (1990)","journal-title":"Order"},{"key":"542_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1017\/S0963548300001139","volume":"3","author":"H Fraysseix de","year":"1994","unstructured":"de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: On triangle contact graphs. Comb. Probab. Comput. 3, 233\u2013246 (1994)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"542_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H Fraysseix de","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)","journal-title":"Combinatorica"},{"key":"542_CR15","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G Battista Di","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs (1999)"},{"issue":"2","key":"542_CR16","doi-asserted-by":"publisher","first-page":"707","DOI":"10.7155\/jgaa.00376","volume":"19","author":"E Giacomo Di","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)","journal-title":"J. Graph Algorithms Appl."},{"key":"542_CR17","doi-asserted-by":"crossref","unstructured":"Di Giacomo, E., Liotta, G., Montecchiani, F.: 1-bend upward planar drawings of SP-digraphs. In: Hu, Y., N\u00f6llenburg, M. (eds.), Graph Drawing, vol. 9801 of LNCS, pp. 123\u2013130. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-50106-2_10"},{"key":"542_CR18","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2017.12.004","volume":"714","author":"E Giacomo Di","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)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"542_CR19","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/j.comgeo.2006.09.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)","journal-title":"Comput. Geom."},{"issue":"3","key":"542_CR20","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.comgeo.2006.08.002","volume":"38","author":"V Dujmovi\u0107","year":"2007","unstructured":"Dujmovi\u0107, V., Suderman, M., Wood, D.R.: Graph drawings with few slopes. Comput. Geom. 38(3), 181\u2013193 (2007)","journal-title":"Comput. Geom."},{"issue":"2","key":"542_CR21","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s00454-012-9472-y","volume":"49","author":"CA Duncan","year":"2013","unstructured":"Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., N\u00f6llenburg, M.: Drawing trees with perfect angular resolution and polynomial area. Discrete Comput. Geom. 49(2), 157\u2013182 (2013)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"542_CR22","doi-asserted-by":"publisher","first-page":"311","DOI":"10.7155\/jgaa.00073","volume":"7","author":"CA Duncan","year":"2003","unstructured":"Duncan, C.A., Kobourov, S.G.: Polar coordinate drawing of planar graphs with good angular resolution. J. Graph Algorithms Appl. 7(4), 311\u2013333 (2003)","journal-title":"J. Graph Algorithms Appl."},{"key":"542_CR23","doi-asserted-by":"crossref","unstructured":"Durocher, S., Mondal, D.: On balanced +-contact representations. In: Graph Drawing, vol. 8242 of LNCS, pp. 143\u2013154. Springer, Berlin (2013)","DOI":"10.1007\/978-3-319-03841-4_13"},{"key":"542_CR24","doi-asserted-by":"crossref","unstructured":"Durocher, S., Mondal, D.: Trade-offs in planar polyline drawings. In: Duncan, C.A., Symvonis, A. (eds.) Graph Drawing, vol. 8871 of LNCS, pp. 306\u2013318. Springer, Berlin (2014)","DOI":"10.1007\/978-3-662-45803-7_26"},{"issue":"3","key":"542_CR25","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1016\/j.comgeo.2013.03.002","volume":"47","author":"S Felsner","year":"2014","unstructured":"Felsner, S., Kaufmann, M., Valtr, P.: Bend-optimal orthogonal graph drawing in the general position model. Comput. Geom. 47(3), 460\u2013468 (2014)","journal-title":"Comput. Geom."},{"issue":"5","key":"542_CR26","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1137\/0222063","volume":"22","author":"M Formann","year":"1993","unstructured":"Formann, M., Hagerup, T., Haralambides, J., Kaufmann, M., Leighton, F.T., Symvonis, A., Welzl, E., Woeginger, G.J.: Drawing graphs in the plane with high resolution. SIAM J. Comput. 22(5), 1035\u20131052 (1993)","journal-title":"SIAM J. Comput."},{"key":"542_CR27","doi-asserted-by":"crossref","unstructured":"Garg, A., Tamassia, R.: Planar drawings and angular resolution: algorithms and bounds (extended abstract). In: van Leeuwen, J. (ed.) ESA, vol. 855 of LNCS, pp. 12\u201323. Springer, Berlin (1994)","DOI":"10.1007\/BFb0049393"},{"issue":"2","key":"542_CR28","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":"542_CR29","doi-asserted-by":"crossref","unstructured":"Gronemann, M.: Bitonic $$st$$ st -orderings of biconnected planar graphs. In: Graph Drawing, vol. 8871 of LNCS, pp. 162\u2013173. Springer, Berlin (2014)","DOI":"10.1007\/978-3-662-45803-7_14"},{"key":"542_CR30","doi-asserted-by":"crossref","unstructured":"Gutwenger, C., Mutzel, P.: Planar polyline drawings with good angular resolution. In: Graph Drawing, vol. 1547 of LNCS, pp. 167\u2013182. Springer, Berlin (1998)","DOI":"10.1007\/3-540-37623-2_13"},{"key":"542_CR31","doi-asserted-by":"crossref","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed), Graph Drawing, vol. 1984 of LNCS, pp. 77\u201390. Springer, Berlin (2000)","DOI":"10.1007\/3-540-44541-2_8"},{"issue":"2","key":"542_CR32","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)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"542_CR33","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)","journal-title":"Graphs Comb."},{"key":"542_CR34","doi-asserted-by":"crossref","unstructured":"J\u00fcnger, M., Mutzel, P. (eds.): Graph Drawing Software. Springer, Berlin (2004)","DOI":"10.1007\/978-3-642-18638-7"},{"key":"542_CR35","doi-asserted-by":"crossref","unstructured":"Kant, G.: Drawing planar graphs using the lmc-ordering (extended abstract). In: FOCS, pp. 101\u2013110. IEEE Computer Society (1992)","DOI":"10.1109\/SFCS.1992.267814"},{"key":"542_CR36","doi-asserted-by":"crossref","unstructured":"Kant, G.: Hexagonal grid drawings. In: Mayr, E.W. (ed.) WG, vol. 657 of LNCS, pp. 263\u2013276. Springer, Berlin (1992)","DOI":"10.1007\/3-540-56402-0_53"},{"issue":"1","key":"542_CR37","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/BF02086606","volume":"16","author":"G Kant","year":"1996","unstructured":"Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4\u201332 (1996)","journal-title":"Algorithmica"},{"issue":"1","key":"542_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1997.2635","volume":"135","author":"G Kant","year":"1997","unstructured":"Kant, G., Bodlaender, H.L.: Triangulating planar graphs while minimizing the maximum degree. Inf. Comput. 135(1), 1\u201314 (1997)","journal-title":"Inf. Comput."},{"issue":"2","key":"542_CR39","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)","journal-title":"SIAM J. Discrete Math."},{"key":"542_CR40","doi-asserted-by":"crossref","unstructured":"Knauer, K., Walczak, B.: Graph drawings with one bend and few slopes. In: Kranakis, E., Navarro, G., Ch\u00e1vez, E. (eds.), LATIN, vol. 9644 of LNCS, pp. 549\u2013561. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-49529-2_41"},{"issue":"5","key":"542_CR41","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)","journal-title":"Comput. Geom."},{"key":"542_CR42","doi-asserted-by":"crossref","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, vol. 8242 of LNCS, pp. 412\u2013423. Springer, Berlin (2013)","DOI":"10.1007\/978-3-319-03841-4_36"},{"issue":"1\u20133","key":"542_CR43","first-page":"69","volume":"81","author":"Y Liu","year":"1998","unstructured":"Liu, Y., Morgana, A., Simeone, B.: A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid. Discrete Appl. Math. 81(1\u20133), 69\u201391 (1998)","journal-title":"Discrete Appl. Math."},{"key":"542_CR44","doi-asserted-by":"crossref","unstructured":"Mukkamala, P., P\u00e1lv\u00f6lgyi, D.: Drawing cubic graphs with the four basic slopes. In: van Kreveld, M.J., Speckmann, B. (eds.) Graph Drawing, vol. 7034 of LNCS, pp. 254\u2013265. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-25878-7_25"},{"key":"542_CR45","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":"542_CR46","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)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"1","key":"542_CR47","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)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"3","key":"542_CR48","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."},{"key":"542_CR49","doi-asserted-by":"crossref","unstructured":"Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization. CRC Press, Amsterdam (2013)","DOI":"10.1201\/b15385"},{"issue":"2","key":"542_CR50","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1093\/comjnl\/37.2.139","volume":"37","author":"GA Wade","year":"1994","unstructured":"Wade, G.A., Chu, J.: Drawability of complete graphs using a minimal slope set. Comput. J. 37(2), 139\u2013142 (1994)","journal-title":"Comput. J."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00542-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-00542-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00542-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,22]],"date-time":"2020-11-22T01:46:57Z","timestamp":1606009617000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-00542-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,8]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["542"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-00542-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,8]]},"assertion":[{"value":"24 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}