{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:41:29Z","timestamp":1742384489514},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405344"},{"type":"electronic","value":"9783540450719"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45071-8_38","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T08:04:43Z","timestamp":1193472283000},"page":"374-384","source":"Crossref","is-referenced-by-count":12,"title":["Efficient Construction of Low Weight Bounded Degree Planar Spanner"],"prefix":"10.1007","author":[{"given":"Xiang-Yang","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"Bose, P., Gudmundsson, J., Smid, M.: Constructing plane spanners of bounded degree and low weight. In: Proceedings of European Symposium of Algorithms. (2002)","DOI":"10.1007\/3-540-45749-6_24"},{"key":"38_CR2","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF02523237","volume":"17","author":"S. Arya","year":"1997","unstructured":"Arya, S., Smid, M.: Efficient construction of a bounded degree spanner with low weight. Algorithmica 17 (1997) 33\u201354","journal-title":"Algorithmica"},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, D., Salowe, J., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proc. 27th ACM STOC. (1995) 489\u2013498","DOI":"10.1145\/225058.225191"},{"key":"38_CR4","unstructured":"Levcopoulos, C., Narasimhan, G., Smid, M.: Improved algorithms for constructing fault tolerant geometric spanners. Algorithmica (2000)"},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. In: Proc. 8th Annual ACM Symposium on Computational Geometry. (1992) 192\u2013201","DOI":"10.1145\/142675.142717"},{"key":"38_CR6","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1142\/S0218195997000193","volume":"7","author":"G. Das","year":"1997","unstructured":"Das, G., Narasimhan, G.: A fast algorithm for constructing sparse euclidean spanners. International Journal on Computational Geometry and Applications 7 (1997) 297\u2013315","journal-title":"International Journal on Computational Geometry and Applications"},{"key":"38_CR7","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Improved greedy algorithms for constructing sparse geometric spanners. In: Scandinavian Workshop on Algorithm Theory. (2000) 314\u2013327","DOI":"10.1007\/3-540-44985-X_28"},{"key":"38_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/3-540-48447-7_20","volume-title":"Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS\u201999)","author":"T. Lukovszki","year":"1999","unstructured":"Lukovszki, T.: New results on fault tolerant geometric spanners. Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS\u201999), LNCS (1999) 193\u2013204"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"Bose, P., Devroye, L., Evans, W., Kirkpatrick, D.: On the spanning ratio of Gabriel graphs and \u03b2-skeletons. In: Proc. of the Latin American Theoretical Infocomatics (LATIN). (2002)","DOI":"10.1007\/3-540-45995-2_42"},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"1502","DOI":"10.1109\/5.163414","volume":"80","author":"J. Jaromczyk","year":"1992","unstructured":"Jaromczyk, J., Toussaint, G.: Relative neighborhood graphs and their relatives. Proceedings of IEEE 80 (1992) 1502\u20131517","journal-title":"Proceedings of IEEE"},{"key":"38_CR11","doi-asserted-by":"publisher","first-page":"259","DOI":"10.2307\/2412323","volume":"18","author":"K. Gabriel","year":"1969","unstructured":"Gabriel, K., Sokal, R.: A new statistical approach to geographic variation analysis. Systematic Zoology 18 (1969) 259\u2013278","journal-title":"Systematic Zoology"},{"key":"38_CR12","series-title":"Technical Report","volume-title":"\u03b2-skeletons have unbounded dilation","author":"D. Eppstein","year":"1996","unstructured":"Eppstein, D.: \u03b2-skeletons have unbounded dilation. Technical Report ICS-TR-96-15, University of California, Irvine (1996)"},{"key":"38_CR13","unstructured":"Dobkin, D., Friedman, S., Supowit, K.: Delaunay graphs are almost as good as complete graphs. Discr. Comp. Geom. (1990) 399\u2013407"},{"key":"38_CR14","series-title":"Lect Notes Comput Sci","volume-title":"Proc. 1st Workshop Algorithms Data Structure","author":"J. Keil","year":"1989","unstructured":"Keil, J., Gutwin, C.: The Delaunay triangulation closely approximates the complete euclidean graph. In: Proc. 1st Workshop Algorithms Data Structure (LNCS 382). (1989)"},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF02187821","volume":"7","author":"J.M. Keil","year":"1992","unstructured":"Keil, J.M., Gutwin, C.A.: Classes of graphs which approximate the complete euclidean graph. Discr. Comp. Geom. 7 (1992) 13\u201328","journal-title":"Discr. Comp. Geom."},{"key":"38_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-51859-2_15","volume-title":"Proceedings of International Symposium on Optimal Algorithms","author":"G. Das","year":"1989","unstructured":"Das, G., Joseph, D.: Which triangulations approximate the complete graph? In: Proceedings of International Symposium on Optimal Algorithms (LNCS 401). (1989) 168\u2013192"},{"key":"38_CR17","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 (1992) 251\u2013256","journal-title":"Algorithmica"},{"key":"38_CR18","unstructured":"Bose, P., Gudmundsson, J., Morin, P.: Ordered \u03d1 graphs. In: Proc. of the Canadian Conf. on Computational Geometry (CCCG). (2002)"},{"key":"38_CR19","doi-asserted-by":"crossref","unstructured":"Bose, P., Morin, P.: Online routing in triangulations. In: Proc. of the 10 th Annual Int. Symp. on Algorithms and Computation ISAAC. (1999)","DOI":"10.1007\/3-540-46632-0_12"},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"Li, X.Y., Wang, Y.: Localized construction of bounded degree planar spanner for wireless networks (2003) Submitted for publication.","DOI":"10.1007\/3-540-45071-8_38"},{"key":"38_CR21","unstructured":"Li, X.Y., Calinescu, G., Wan, P.J.: Distributed construction of planar spanner and routing for ad hoc wireless networks. In: 21st IEEE INFOCOM. Volume 3. (2002)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45071-8_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T14:58:30Z","timestamp":1684076310000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45071-8_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405344","9783540450719"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-45071-8_38","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}