{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T03:12:15Z","timestamp":1743131535589,"version":"3.40.3"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319292205"},{"type":"electronic","value":"9783319292212"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-29221-2_12","type":"book-chapter","created":{"date-parts":[[2016,2,12]],"date-time":"2016-02-12T12:02:54Z","timestamp":1455278574000},"page":"139-151","source":"Crossref","is-referenced-by-count":4,"title":["Lower Bounds on the Dilation of Plane Spanners"],"prefix":"10.1007","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[]},{"given":"Anirban","family":"Ghosh","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1\u20133","key":"12_CR1","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s00454-007-9019-9","volume":"39","author":"PK Agarwal","year":"2008","unstructured":"Agarwal, P.K., Klein, R., Knauer, C., Langerman, S., Morin, P., Sharir, M., Soss, M.: Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D. Discrete Comput. Geom. 39(1\u20133), 17\u201337 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9, 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Amarnadh, N., Mitra, P.: Upper bound on dilation of triangulations of cyclic polygons. In: Proceedings of the Conference Computational Science and Applications, pp. 1\u20139. Springer (2006)","DOI":"10.1007\/11751540_1"},{"issue":"3","key":"12_CR4","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.comgeo.2007.07.004","volume":"40","author":"B Aronov","year":"2008","unstructured":"Aronov, B., de Berg, M., Cheong, O., Gudmundsson, J., Haverkort, H.J., Vigneron, A.: Sparse geometric graphs with small dilation. Comput. Geom. 40(3), 207\u2013219 (2008)","journal-title":"Comput. Geom."},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-642-14165-2_3","volume-title":"Automata, Languages and Programming","author":"N Bonichon","year":"2010","unstructured":"Bonichon, N., Gavoille, C., Hanusse, N., Perkovi\u0107, L.: Plane spanners of maximum degree six. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 19\u201330. Springer, Heidelberg (2010)"},{"issue":"3","key":"12_CR6","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/s00454-015-9676-z","volume":"53","author":"N Bonichon","year":"2015","unstructured":"Bonichon, N., Kanj, I., Perkovi\u0107, L., Xia, G.: There are plane spanners of degree 4 and moderate stretch factor. Discrete Comput. Geom. 53(3), 514\u2013546 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.jda.2012.03.004","volume":"15","author":"P Bose","year":"2012","unstructured":"Bose, P., Carmi, P., Chaitman-Yerushalmi, L.: On bounded degree plane strong geometric spanners. J. Discrete Algorithms 15, 16\u201331 (2012)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"12_CR8","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 \n                    \n                      \n                    \n                    $$\\pi \/2$$\n                  . Comput. Geom. 44(2), 121\u2013127 (2011)","journal-title":"Comput. Geom."},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00453-005-1168-8","volume":"42","author":"P Bose","year":"2005","unstructured":"Bose, P., Gudmundsson, J., Smid, M.: Constructing plane spanners of bounded degree and low weight. Algorithmica 42, 249\u2013264 (2005)","journal-title":"Algorithmica"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-540-73951-7_29","volume-title":"Algorithms and Data Structures","author":"P Bose","year":"2007","unstructured":"Bose, P., Lee, A., Smid, M.: On generalized diamond spanners. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 325\u2013336. Springer, Heidelberg (2007)"},{"issue":"7","key":"12_CR11","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."},{"issue":"2","key":"12_CR12","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1142\/S0218195909002861","volume":"19","author":"P Bose","year":"2009","unstructured":"Bose, P., Smid, M., Xu, D.: Delaunay and diamond triangulations contain spanners of bounded degree. Internat. J. Comput. Geom. Appl. 19(2), 119\u2013140 (2009)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1142\/S0218195995000088","volume":"5","author":"B Chandra","year":"1995","unstructured":"Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. Internat. J. Comput. Geom. Appl. 5, 125\u2013144 (1995)","journal-title":"Internat. J. Comput. Geom. Appl."},{"issue":"3","key":"12_CR14","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.comgeo.2007.12.001","volume":"41","author":"O Cheong","year":"2008","unstructured":"Cheong, O., Herman, H., Lee, M.: Computing a minimum-dilation spanning tree is NP-hard. Comput. Geom. 41(3), 188\u2013205 (2008)","journal-title":"Comput. Geom."},{"issue":"2","key":"12_CR15","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"P Chew","year":"1989","unstructured":"Chew, P.: There are planar graphs almost as good as the complete graph. J. Comput. Syst. Sci. 39(2), 205\u2013219 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"12_CR16","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.comgeo.2010.09.007","volume":"44","author":"S Cui","year":"2011","unstructured":"Cui, S., Kanj, I., Xia, G.: On the stretch factor of Delaunay triangulations of points in convex position. Comput. Geom. 44(2), 104\u2013109 (2011)","journal-title":"Comput. Geom."},{"issue":"2","key":"12_CR17","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1142\/S0129054196000105","volume":"7","author":"G Das","year":"1996","unstructured":"Das, G., Heffernan, P.: Constructing degree-3 spanners with other sparseness properties. Internat. J. Found. Comput. Sci. 7(2), 121\u2013136 (1996)","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/3-540-51859-2_15","volume-title":"Optimal Algorithms","author":"G Das","year":"1989","unstructured":"Das, G., Joseph, D.: Which triangulations approximate the complete graph? In: Djidjev, H.N. (ed.) Optimal Algorithms. LNCS, vol. 401, pp. 168\u2013192. Springer, Heidelberg (1989)"},{"key":"12_CR19","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, 399\u2013407 (1990)","journal-title":"Discrete Comput. Geom."},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.comgeo.2005.07.004","volume":"36","author":"A Dumitrescu","year":"2006","unstructured":"Dumitrescu, A., Ebbers-Baumann, A., Gr\u00fcne, A., Klein, R., Rote, G.: On the geometric dilation of closed curves, graphs, and point sets. Comput. Geom. 36, 16\u201338 (2006)","journal-title":"Comput. Geom."},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Dumitrescu, A., Ghosh, A.: Lower bounds on the dilation of plane spanners, October 2015. \n                    arXiv:1509.07181","DOI":"10.1007\/978-3-319-29221-2_12"},{"key":"12_CR22","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/978-3-319-29221-2_13","volume-title":"Algorithms and Discrete Applied Mathematics","author":"Adrian Dumitrescu","year":"2016","unstructured":"Dumitrescu, A., Ghosh, A.: Lattice spanners of low degree. In: Govindarajan, S., Maheshwari, A. (eds.) CALDAM 2016. LNCS, Vol. 9602, pp. 152\u2013163. Springer, Switzerland (2016)"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s00453-005-1203-9","volume":"44","author":"A Ebbers-Baumann","year":"2006","unstructured":"Ebbers-Baumann, A., Gr\u00fcne, A., Klein, R.: On the geometric dilation of finite point sets. Algorithmica 44, 137\u2013149 (2006)","journal-title":"Algorithmica"},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0925-7721(03)00046-4","volume":"27","author":"A Ebbers-Baumann","year":"2004","unstructured":"Ebbers-Baumann, A., Klein, R., Langetepe, E., Lingas, A.: A fast algorithm for approximating the detour of a polygonal chain. Comput. Geom. 27, 123\u2013134 (2004)","journal-title":"Comput. Geom."},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Spanning trees and spanners, in Handbook of Computational Geometry (Sack, J.R., Urrutia, J. (Eds)), pp. 425\u2013461. Amsterdam (2000)","DOI":"10.1016\/B978-044482537-7\/50010-3"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., Knauer, C.: Dilation and detour in geometric networks, in handbook on approximation algorithms and metaheuristics, Chapter 52 (Gonzalez,T. (Eds.), Chapman & Hall\/CRC, Boca Raton (2007)","DOI":"10.1201\/9781420010749.ch52"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Kanj, I.: Geometric spanners: recent results and open directions. In: Proceedings of the 3rd International Conference on Communication and Information Technology, pp. 78\u201382. IEEE (2013)","DOI":"10.1109\/ICCITechnology.2013.6579526"},{"key":"12_CR28","unstructured":"Kanj, I., Perkovi\u0107, L.: On geometric spanners of Euclidean and unit disk graphs. In: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp. 409\u2013420 (2008)"},{"key":"12_CR29","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF02187821","volume":"7","author":"M Keil","year":"1992","unstructured":"Keil, M., Gutwin, C.A.: Classes of graphs which approximate the complete Euclidean graph. Discrete Comput. Geom. 7, 13\u201328 (1992)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"12_CR30","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/s00454-014-9651-0","volume":"53","author":"R Klein","year":"2015","unstructured":"Klein, R., Kutz, M., Penninger, R.: Most finite point sets in the plane have dilation \n                    \n                      \n                    \n                    $$>$$\n                   1. Discrete Comput. Geom. 53(1), 80\u2013106 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"12_CR31","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01758846","volume":"8","author":"C Levcopoulos","year":"1992","unstructured":"Levcopoulos, C., Lingas, A.: There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees. Algorithmica 8, 251\u2013256 (1992)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"12_CR32","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1142\/S0218195904001366","volume":"14","author":"XY Li","year":"2004","unstructured":"Li, X.Y., Wang, Y.: Efficient construction of low weight bounded degree planar spanner. Internat. J. Comput. Geom. Appl. 14(1\u20132), 69\u201384 (2004)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"12_CR33","unstructured":"Mulzer, W.: Minimum dilation triangulations for the regular \n                    \n                      \n                    \n                    $$n$$\n                  -gon, Masters thesis, Freie Universit\u00e4t, Berlin (2004)"},{"key":"12_CR34","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)"},{"issue":"3","key":"12_CR35","doi-asserted-by":"publisher","first-page":"457","DOI":"10.7155\/jgaa.00234","volume":"15","author":"MT Parvez","year":"2011","unstructured":"Parvez, M.T., Rahman, M.S., Nakano, S.-I.: Generating all triangulations of plane graphs. J. Graph. Algorithms Appl. 15(3), 457\u2013482 (2011)","journal-title":"J. Graph. Algorithms Appl."},{"issue":"4","key":"12_CR36","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 1998. SIAM J. Comput. 42(4), 1620\u20131659 (2013)","journal-title":"SIAM J. Comput."},{"key":"12_CR37","doi-asserted-by":"crossref","unstructured":"Xia, G., Zhang, L.: Toward the tight bound of the stretch factor of delaunay triangulations. In: Proceedings of the 23rd Canadian Conference on Computer Geometry (2011)","DOI":"10.1145\/1998196.1998235"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-29221-2_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T09:59:17Z","timestamp":1559383157000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-29221-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319292205","9783319292212"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-29221-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}