{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:03:35Z","timestamp":1709823815808},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p> Given a triangulation G, whose vertex set V is a set of n points in the plane, and given a real number \u03b3 with 0 &lt; \u03b3 &lt; \u03c0, we design an O(n)-time algorithm that constructs a connected subgraph G' of G with vertex set V whose maximum degree is at most 14 + \u23082\u03c0\/\u03b3\u2309. If G is the Delaunay triangulation of V, and \u03b3 = 2\u03c0\/3, we show that G' is a t-spanner of V (for some constant t) with maximum degree at most 17, thereby improving the previously best known degree bound of 23. If G is a triangulation satisfying the diamond property, then for a specific range of values of \u03b3 dependent on the angle of the diamonds, we show that G' is a t-spanner of V (for some constant t) whose maximum degree is bounded by a constant dependent on \u03b3. If G is the graph consisting of all Delaunay edges of length at most 1, and \u03b3 = \u03c0\/3, we show that a modified version of the algorithm produces a plane subgraph G' of the unit-disk graph which is a t-spanner (for some constant t) of the unit-disk graph of V, whose maximum degree is at most 20, thereby improving the previously best known degree bound of 25. <\/jats:p>","DOI":"10.1142\/s0218195909002861","type":"journal-article","created":{"date-parts":[[2009,5,5]],"date-time":"2009-05-05T11:30:21Z","timestamp":1241523021000},"page":"119-140","source":"Crossref","is-referenced-by-count":21,"title":["DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE"],"prefix":"10.1142","volume":"19","author":[{"given":"PROSENJIT","family":"BOSE","sequence":"first","affiliation":[{"name":"School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MICHIEL","family":"SMID","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DAMING","family":"XU","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1168-8"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.04.003"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369387"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90044-5"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187801"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187821"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195904001366"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195909002861","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:22:34Z","timestamp":1565137354000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195909002861"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":8,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1142\/S0218195909002861"],"URL":"https:\/\/doi.org\/10.1142\/s0218195909002861","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4]]}}}