{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:25Z","timestamp":1740109585562,"version":"3.37.3"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T00:00:00Z","timestamp":1654473600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T00:00:00Z","timestamp":1654473600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100010665","name":"H2020 Marie Sk\u0142odowska-Curie Actions","doi-asserted-by":"publisher","award":["734922"],"award-info":[{"award-number":["734922"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"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"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00454-022-00398-5","type":"journal-article","created":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T15:02:57Z","timestamp":1654527777000},"page":"774-795","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Drawing Graphs as Spanners"],"prefix":"10.1007","volume":"68","author":[{"given":"Oswin","family":"Aichholzer","sequence":"first","affiliation":[]},{"given":"Manuel","family":"Borrazzo","sequence":"additional","affiliation":[]},{"given":"Prosenjit","family":"Bose","sequence":"additional","affiliation":[]},{"given":"Jean","family":"Cardinal","sequence":"additional","affiliation":[]},{"given":"Fabrizio","family":"Frati","sequence":"additional","affiliation":[]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[]},{"given":"Birgit","family":"Vogtenhuber","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,6]]},"reference":[{"key":"398_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R}$$-complete. In: 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018), pp. 65\u201373. ACM, New York (2018)","DOI":"10.1145\/3188745.3188868"},{"issue":"2","key":"398_CR2","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/0097-3165(95)90058-6","volume":"69","author":"DM Acketa","year":"1995","unstructured":"Acketa, D.M., \u017duni\u0107, J.D.: On the maximal number of edges of convex digital polygons included into an $$m\\times m$$-grid. J. Comb. Theory Ser. A 69(2), 358\u2013368 (1995)","journal-title":"J. Comb. Theory Ser. A"},{"key":"398_CR3","doi-asserted-by":"crossref","unstructured":"Alamdari, S., Chan, T.M., Grant, E., Lubiw, A., Pathak, V.: Self-approaching graphs. In: 20th International Symposium on Graph Drawing (Redmond 2012). Lecture Notes in Computer Science, vol. 7704, pp. 260\u2013271. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-36763-2_23"},{"issue":"2B","key":"398_CR4","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.comgeo.2012.10.011","volume":"47","author":"P Angelini","year":"2014","unstructured":"Angelini, P., Bruckdorfer, T., Chiesa, M., Frati, F., Kaufmann, M., Squarcella, C.: On the area requirements of Euclidean minimum spanning trees. Comput. Geom. 47(2B), 200\u2013213 (2014)","journal-title":"Comput. Geom."},{"issue":"1","key":"398_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.7155\/jgaa.00249","volume":"16","author":"P Angelini","year":"2012","unstructured":"Angelini, P., Colasante, E., Di Battista, G., Frati, F., Patrignani, M.: Monotone drawings of graphs. J. Graph Algorithms Appl. 16(1), 5\u201335 (2012)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"398_CR6","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1002\/net.21449","volume":"59","author":"P Angelini","year":"2012","unstructured":"Angelini, P., Di Battista, G., Frati, F.: Succinct greedy drawings do not always exist. Networks 59(3), 267\u2013274 (2012)","journal-title":"Networks"},{"issue":"2","key":"398_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00453-013-9790-3","volume":"71","author":"P Angelini","year":"2015","unstructured":"Angelini, P., Didimo, W., Kobourov, S., Mchedlidze, T., Roselli, V., Symvonis, A., Wismath, S.: Monotone drawings of graphs with fixed embedding. Algorithmica 71(2), 233\u2013257 (2015)","journal-title":"Algorithmica"},{"issue":"1","key":"398_CR8","doi-asserted-by":"publisher","first-page":"19","DOI":"10.7155\/jgaa.00197","volume":"14","author":"P Angelini","year":"2010","unstructured":"Angelini, P., Frati, F., Grilli, L.: An algorithm to construct greedy drawings of triangulations. J. Graph Algorithms Appl. 14(1), 19\u201351 (2010)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"398_CR9","doi-asserted-by":"publisher","first-page":"97","DOI":"10.7155\/jgaa.00219","volume":"15","author":"M Badent","year":"2011","unstructured":"Badent, M., Brandes, U., Cornelsen, S.: More canonical ordering. J. Graph Algorithms Appl. 15(1), 97\u2013126 (2011)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"398_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-006-0649-0","volume":"22","author":"D Bauer","year":"2006","unstructured":"Bauer, D., Broersma, H., Schmeichel, E.: Toughness in graphs\u2014a survey. Graphs Comb. 22(1), 1\u201335 (2006)","journal-title":"Graphs Comb."},{"key":"398_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03427-9","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"1997","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, Berlin (1997)"},{"key":"398_CR12","doi-asserted-by":"crossref","unstructured":"Bonichon, N., Bose, P., Carmi, P., Kostitsyna, I., Lubiw,\u00a0A., Verdonschot,\u00a0S.: Gabriel triangulations and angle-monotone graphs: local routing and recognition. In: 24th International Symposium on Graph Drawing and Network Visualization (Athens 2016). Lecture Notes in Computer Science, vol. 9801, pp. 519\u2013531. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-50106-2_40"},{"issue":"4","key":"398_CR13","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s00453-006-0177-6","volume":"47","author":"N Bonichon","year":"2007","unstructured":"Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of $$3$$-connected plane graphs. Algorithmica 47(4), 399\u2013420 (2007)","journal-title":"Algorithmica"},{"issue":"2","key":"398_CR14","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.comgeo.2010.09.009","volume":"44","author":"P Bose","year":"2011","unstructured":"Bose, P., Devroye, L., L\u00f6ffler, M., Snoeyink, J., Verma, V.: Almost all Delaunay triangulations have stretch factor greater than $$\\pi \/2$$. Comput. Geom. 44(2), 121\u2013127 (2011)","journal-title":"Comput. Geom."},{"key":"398_CR15","doi-asserted-by":"crossref","unstructured":"Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S.: Competitive routing in the half-$$\\theta _6$$-graph. In: 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (Kyoto 2012), pp. 1319\u20131328. ACM, New York (2012)","DOI":"10.1137\/1.9781611973099.104"},{"issue":"4","key":"398_CR16","doi-asserted-by":"publisher","first-page":"1392","DOI":"10.1007\/s00453-018-0476-8","volume":"81","author":"P Bose","year":"2019","unstructured":"Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S.: On plane constrained bounded-degree spanners. Algorithmica 81(4), 1392\u20131415 (2019)","journal-title":"Algorithmica"},{"issue":"7","key":"398_CR17","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1016\/j.comgeo.2013.04.002","volume":"46","author":"P Bose","year":"2013","unstructured":"Bose, P., Smid, M.: On plane geometric spanners: a survey and open problems. Comput. Geom. 46(7), 818\u2013830 (2013)","journal-title":"Comput. Geom."},{"key":"398_CR18","doi-asserted-by":"crossref","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: 20th Annual ACM Symposium on Theory of Computing (Chicago 1988), pp. 460\u2013467. ACM, New York (1988)","DOI":"10.1145\/62212.62257"},{"issue":"1","key":"398_CR19","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/s00454-016-9831-1","volume":"57","author":"J Cardinal","year":"2017","unstructured":"Cardinal, J., Hoffmann, U.: Recognition and complexity of point visibility graphs. Discrete Comput. Geom. 57(1), 164\u2013178 (2017)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"398_CR20","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"LP Chew","year":"1989","unstructured":"Chew, L.P.: There are planar graphs almost as good as the complete graph. J. Comput. System Sci. 39(2), 205\u2013219 (1989)","journal-title":"J. Comput. System Sci."},{"key":"398_CR21","unstructured":"Chiang, Y.-T., Lin, C.-C., Lu, H.-I.: Orderly spanning trees with applications to graph encoding and graph drawing. In: 12th Annual ACM-SIAM Symposium on Discrete Algorithms (Washington 2001), pp. 506\u2013515. SIAM, Philadelphia (2001)"},{"issue":"3","key":"398_CR22","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0012-365X(73)90138-6","volume":"5","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Tough graphs and Hamiltonian circuits. Discrete Math. 5(3), 215\u2013228 (1973)","journal-title":"Discrete Math."},{"key":"398_CR23","unstructured":"Da Lozzo, G., D\u2019Angelo, A., Frati, F.: On planar greedy drawings of $$3$$-connected planar graphs. In: 33rd International Symposium on Computational Geometry (Brisbane 2017). Leibniz International Proceedings in Informatics, vol. 77, #\u00a033. Leibniz-Zent. Inform., Wadern (2017)"},{"issue":"2","key":"398_CR24","doi-asserted-by":"publisher","first-page":"761","DOI":"10.7155\/jgaa.00348","volume":"19","author":"HR Dehkordi","year":"2015","unstructured":"Dehkordi, H.R., Frati, F., Gudmundsson, J.: Increasing-chord graphs on point sets. J. Graph Algorithms Appl. 19(2), 761\u2013778 (2015)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"398_CR25","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/j.jcss.2011.06.001","volume":"78","author":"E Di Giacomo","year":"2012","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H.: Drawing a tree as a minimum spanning tree approximation. J. Comput. Syst. Sci. 78(2), 491\u2013503 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"398_CR26","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/BF02187801","volume":"5","author":"DP Dobkin","year":"1990","unstructured":"Dobkin, D.P., Friedman, S.J., Supowit, K.J.: Delaunay graphs are almost as good as complete graphs. Discrete Comput. Geom. 5(4), 399\u2013407 (1990)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"398_CR27","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":"2","key":"398_CR28","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1142\/S0218195916500059","volume":"26","author":"A Dumitrescu","year":"2016","unstructured":"Dumitrescu, A., Ghosh, A.: Lower bounds on the dilation of plane spanners. Int. J. Comput. Geom. Appl. 26(2), 89\u2013110 (2016)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"11","key":"398_CR29","doi-asserted-by":"publisher","first-page":"1571","DOI":"10.1109\/TC.2010.257","volume":"60","author":"D Eppstein","year":"2011","unstructured":"Eppstein, D., Goodrich, M.T.: Succinct greedy geometric routing using hyperbolic geometry. IEEE Trans. Comput. 60(11), 1571\u20131580 (2011)","journal-title":"IEEE Trans. Comput."},{"key":"398_CR30","unstructured":"Felsner, S., Igamberdiev, A., Kindermann, P., Klemz,\u00a0B., Mchedlidze,\u00a0T., Scheucher,\u00a0M.: Strongly monotone drawings of planar graphs. In: 32nd International Symposium on Computational Geometry (Boston 2016). Leibniz International Proceedings in Informatics, vol.\u00a051, #\u00a037. Leibniz-Zent. Inform., Wadern (2016)"},{"issue":"9","key":"398_CR31","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1016\/j.comgeo.2011.05.005","volume":"44","author":"F Frati","year":"2011","unstructured":"Frati, F., Kaufmann, M.: Polynomial area bounds for MST embeddings of trees. Comput. Geom. 44(9), 529\u2013543 (2011)","journal-title":"Comput. Geom."},{"issue":"1","key":"398_CR32","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)","journal-title":"Combinatorica"},{"key":"398_CR33","series-title":"A Series of Books in the Mathematical Sciences","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences, W.H. Freeman, San Francisco (1979)"},{"issue":"4","key":"398_CR34","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"398_CR35","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/PL00009189","volume":"20","author":"D Harel","year":"1998","unstructured":"Harel, D., Sardas, M.: An algorithm for straight-line drawing of planar graphs. Algorithmica 20(2), 119\u2013135 (1998)","journal-title":"Algorithmica"},{"issue":"3","key":"398_CR36","doi-asserted-by":"publisher","first-page":"1867","DOI":"10.1137\/16M1080045","volume":"31","author":"D He","year":"2017","unstructured":"He, D., He, X.: Optimal monotone drawings of trees. SIAM J. Discrete Math. 31(3), 1867\u20131877 (2017)","journal-title":"SIAM J. Discrete Math."},{"key":"398_CR37","doi-asserted-by":"crossref","unstructured":"He, X., He, D.: Monotone drawings of $$3$$-connected plane graphs. In: 23rd Annual European Symposium on Algorithms (Patras 2015). Lecture Notes in Computer Science, vol. 9294, pp. 729\u2013741. Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-662-48350-3_61"},{"issue":"2","key":"398_CR38","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s00453-012-9682-y","volume":"68","author":"X He","year":"2014","unstructured":"He, X., Zhang, H.: On succinct greedy drawings of plane triangulations and $$3$$-connected plane graphs. Algorithmica 68(2), 531\u2013544 (2014)","journal-title":"Algorithmica"},{"issue":"2","key":"398_CR39","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.tcs.2015.09.004","volume":"607","author":"MdI Hossain","year":"2015","unstructured":"Hossain, Md.I., Rahman, Md.S.: Good spanning trees in graph drawing. Theoret. Comput. Sci. 607(2), 149\u2013165 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"398_CR40","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1017\/S0305004198003016","volume":"125","author":"Ch Icking","year":"1999","unstructured":"Icking, Ch., Klein, R., Langetepe, E.: Self-approaching curves. Math. Proc. Camb. Philos. Soc. 125(3), 441\u2013453 (1999)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"issue":"1","key":"398_CR41","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"},{"key":"398_CR42","doi-asserted-by":"crossref","unstructured":"Kindermann, P., Schulz, A., Spoerhase, J., Wolff, A.: On monotone drawings of trees. In: 22nd International Symposium on Graph Drawing (W\u00fcrzburg 2014). Lecture Notes in Computer Science, vol. 8871, pp. 488\u2013500. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-662-45803-7_41"},{"issue":"3","key":"398_CR43","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1007\/s00454-009-9227-6","volume":"44","author":"T Leighton","year":"2010","unstructured":"Leighton, T., Moitra, A.: Some results on greedy embeddings in metric spaces. Discrete Comput. Geom. 44(3), 686\u2013705 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"398_CR44","doi-asserted-by":"publisher","first-page":"345","DOI":"10.7155\/jgaa.00494","volume":"23","author":"A Lubiw","year":"2019","unstructured":"Lubiw, A., Mondal, D.: Construction and local routing for angle-monotone graphs. J. Graph Algorithms Appl. 23(2), 345\u2013369 (2019)","journal-title":"J. Graph Algorithms Appl."},{"key":"398_CR45","doi-asserted-by":"crossref","unstructured":"Mn\u00ebv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Topology and Geometry\u2013Rohlin Seminar. Lecture Notes in Mathematics, vol. 1346, pp. 527\u2013543. Springer, Berlin (1988)","DOI":"10.1007\/BFb0082792"},{"issue":"3","key":"398_CR46","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"C Monma","year":"1992","unstructured":"Monma, C., Suri, S.: Transitions in geometric minimum spanning trees. Discrete Comput. Geom. 8(3), 265\u2013293 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"398_CR47","unstructured":"Mulzer, W.J.H.: Minimum Dilation Triangulations for the Regular $$n$$-gon. MSc thesis, Freie Universit\u00e4t Berlin (2004). https:\/\/page.mi.fu-berlin.de\/mulzer\/pubs\/diplom.pdf"},{"issue":"3","key":"398_CR48","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1007\/s00454-017-9913-8","volume":"58","author":"M N\u00f6llenburg","year":"2017","unstructured":"N\u00f6llenburg, M., Prutkin, R.: Euclidean greedy drawings of trees. Discrete Comput. Geom. 58(3), 543\u2013579 (2017)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"398_CR49","first-page":"47","volume":"7","author":"M N\u00f6llenburg","year":"2016","unstructured":"N\u00f6llenburg, M., Prutkin, R., Rutter, I.: On self-approaching and increasing-chord drawings of $$3$$-connected planar graphs. J. Comput. Geom. 7(1), 47\u201369 (2016)","journal-title":"J. Comput. Geom."},{"issue":"1","key":"398_CR50","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2005.06.022","volume":"344","author":"ChH Papadimitriou","year":"2005","unstructured":"Papadimitriou, Ch.H., Ratajczak, D.: On a conjecture related to geometric routing. Theoret. Comput. Sci. 344(1), 3\u201314 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"398_CR51","doi-asserted-by":"crossref","unstructured":"Rao, A., Ratnasamy, S., Papadimitriou, Ch., Shenker, S., Stoica,\u00a0I.: Geographic routing without location information. In: 9th Annual International Conference on Mobile Computing and Networking (San Diego 2003), pp. 96\u2013108. ACM, New York (2003)","DOI":"10.1145\/938985.938996"},{"issue":"1","key":"398_CR52","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0305004100071875","volume":"115","author":"G Rote","year":"1994","unstructured":"Rote, G.: Curves with increasing chords. Math. Proc. Camb. Philos. Soc. 115(1), 1\u201312 (1994)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"398_CR53","doi-asserted-by":"crossref","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: 17th International Symposium on Graph Drawing (Chicago 2009). Lecture Notes in Computer Science, vol. 5849, pp. 334\u2013344. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"398_CR54","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: 1st Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco 1990), pp. 138\u2013148. SIAM, Philadelphia (1990)"},{"key":"398_CR55","unstructured":"Shiloach, Y.: Linear and Planar Arrangements of Graphs. PhD thesis, Weizmann Institute of Science (1976)"},{"issue":"2","key":"398_CR56","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)","journal-title":"IEEE Trans. Comput."},{"key":"398_CR57","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2013.05.024","volume":"532","author":"J-J Wang","year":"2014","unstructured":"Wang, J.-J., He, X.: Succinct strictly convex greedy drawing of $$3$$-connected plane graphs. Theoret. Comput. Sci. 532, 80\u201390 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"398_CR58","doi-asserted-by":"crossref","unstructured":"Win Sein: On a connection between the existence of $$k$$-trees and the toughness of a graph. Graphs Comb. 5(2), 201\u2013205 (1989)","DOI":"10.1007\/BF01788671"},{"issue":"4","key":"398_CR59","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1137\/110832458","volume":"42","author":"G Xia","year":"2013","unstructured":"Xia, G.: The stretch factor of the Delaunay triangulation is less than 1.998. SIAM J. Comput. 42(4), 1620\u20131659 (2013)","journal-title":"SIAM J. Comput."},{"key":"398_CR60","doi-asserted-by":"crossref","unstructured":"Xia, G., Zhang, L.: Toward the tight bound of the stretch factor of Delaunay triangulations. In: 23rd Annual Canadian Conference on Computational Geometry (Toronto 2011), #\u00a057 (2011)","DOI":"10.1145\/1998196.1998235"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00398-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00398-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00398-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T14:34:18Z","timestamp":1727361258000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00398-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,6]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["398"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00398-5","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,6,6]]},"assertion":[{"value":"12 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}