{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:18Z","timestamp":1750306878227,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,17]],"date-time":"2013-06-17T00:00:00Z","timestamp":1371427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,6,17]]},"DOI":"10.1145\/2462356.2462381","type":"proceedings-article","created":{"date-parts":[[2014,1,7]],"date-time":"2014-01-07T17:18:46Z","timestamp":1389115126000},"page":"449-458","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Robust geometric spanners"],"prefix":"10.1145","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[{"name":"Carleton University, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vida","family":"Dujmovi\u0107","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9343-y"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9137-7"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.01.008"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-011-0346-7"},{"key":"e_1_3_2_1_5_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1007\/3-540-61680-2_79","volume-title":"ESA","author":"Arikati S. R.","year":"1996","unstructured":"Arikati , S. R. , Chen , D. Z. , Chew , L. P. , Das , G. , Smid , M. H. M. , and Zaroliagis , C. D . Planar spanners and approximate shortest path queries among obstacles in the plane . In ESA ( 1996 ), J. Diaz and M. J. Serna, Eds ., vol. 1136 of Lecture Notes in Computer Science , Springer , pp. 514 -- 528 . Arikati, S. R., Chen, D. Z., Chew, L. P., Das, G., Smid, M. H. M., and Zaroliagis, C. D. Planar spanners and approximate shortest path queries among obstacles in the plane. In ESA (1996), J. Diaz and M. J. Serna, Eds., vol. 1136 of Lecture Notes in Computer Science, Springer, pp. 514--528."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.07.004"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225191"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365722"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00014-0"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523237"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_3_2_1_12_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/978-3-540-72951-8_3","volume-title":"SIROCCO","author":"Bodlaender H. L.","year":"2007","unstructured":"Bodlaender , H. L. Treewidth: Structure and algorithms . In SIROCCO ( 2007 ), G. Prencipe and S. Zaks, Eds ., vol. 4474 of Lecture Notes in Computer Science , Springer , pp. 11 -- 25 . Bodlaender, H. L. Treewidth: Structure and algorithms. In SIROCCO (2007), G. Prencipe and S. Zaks, Eds., vol. 4474 of Lecture Notes in Computer Science, Springer, pp. 11--25."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.04.003"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9293-4"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29344-3_8"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1168-8"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195909002861"},{"key":"e_1_3_2_1_18_1","volume-title":"Bounded degree planar geometric spanners. CoRR abs\/1003.4963","author":"Carmi P.","year":"2010","unstructured":"Carmi , P. , and Chaitman , L . Bounded degree planar geometric spanners. CoRR abs\/1003.4963 ( 2010 ). Carmi, P., and Chaitman, L. Bounded degree planar geometric spanners. CoRR abs\/1003.4963 (2010)."},{"key":"e_1_3_2_1_19_1","first-page":"31","volume-title":"CCCG","author":"Carmi P.","year":"2010","unstructured":"Carmi , P. , and Chaitman , L . Stable roommates and geometric spanners . In CCCG ( 2010 ), pp. 31 -- 34 . Carmi, P., and Chaitman, L. Stable roommates and geometric spanners. In CCCG (2010), pp. 31--34."},{"key":"e_1_3_2_1_20_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/978-3-642-17517-6_29","volume-title":"ISAAC (1)","author":"Carmi P.","year":"2010","unstructured":"Carmi , P. , and Smid , M. H. M . An optimal algorithm for computing angle-constrained spanners . In ISAAC (1) ( 2010 ), O. Cheong, K .-Y. Chwa, and K. Park, Eds., vol. 6506 of Lecture Notes in Computer Science , Springer , pp. 316 -- 327 . Carmi, P., and Smid, M. H. M. An optimal algorithm for computing angle-constrained spanners. In ISAAC (1) (2010), O. Cheong, K.-Y. Chwa, and K. Park, Eds., vol. 6506 of Lecture Notes in Computer Science, Springer, pp. 316--327."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90044-5"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1121-7"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Das G. and \n      Joseph D\n  . \n  Which triangulations approximate the complete graph? In Optimal Algorithms\n   (\n  1989\n  ) H. Djidjev Ed\n  . vol. \n  401\n   of \n  Lecture Notes in Computer Science Springer pp. \n  168\n  --\n  192\n  .   Das G. and Joseph D. Which triangulations approximate the complete graph? In Optimal Algorithms (1989) H. Djidjev Ed. vol. 401 of Lecture Notes in Computer Science Springer pp. 168--192.","DOI":"10.1007\/3-540-51859-2_15"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195997000193"},{"key":"e_1_3_2_1_25_1","first-page":"425","volume-title":"Eds. Elsevier","author":"Eppstein D.","year":"1999","unstructured":"Eppstein , D. Spanning trees and spanners. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia , Eds. Elsevier , 1999 , ch. 9, pp. 425 -- 461 . Eppstein, D. Spanning trees and spanners. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier, 1999, ch. 9, pp. 425--461."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_2_1_28_1","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1090\/dimacs\/004\/31","volume-title":"Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift","author":"Kalai G.","year":"1991","unstructured":"Kalai , G. The diameter of graphs of convex polytopes and f-vector theory . In Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift , vol. 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science . AMS , 1991 , pp. 387 -- 412 . Kalai, G. The diameter of graphs of convex polytopes and f-vector theory. In Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift , vol. 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. AMS, 1991, pp. 387--412."},{"key":"e_1_3_2_1_29_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-51542-9_6","volume-title":"WADS","author":"Keil J. M.","year":"1989","unstructured":"Keil , J. M. , and Gutwin , C. A . The Delauney triangulation closely approximates the complete Euclidean graph . In WADS ( 1989 ), F. K. H. A. Dehne, J .-R. Sack, and N. Santoro, Eds., vol. 382 of Lecture Notes in Computer Science , Springer , pp. 47 -- 56 . Keil, J. M., and Gutwin, C. A. The Delauney triangulation closely approximates the complete Euclidean graph. In WADS (1989), F. K. H. A. Dehne, J.-R. Sack, and N. Santoro, Eds., vol. 382 of Lecture Notes in Computer Science, Springer, pp. 47--56."},{"key":"e_1_3_2_1_30_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations And Approximations","author":"Kloks T.","year":"1994","unstructured":"Kloks , T. Treewidth: Computations And Approximations . Lecture Notes in Computer Science . Springer-Verlag , 1994 . Kloks, T. Treewidth: Computations And Approximations. Lecture Notes in Computer Science. Springer-Verlag, 1994."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0075-x"},{"key":"e_1_3_2_1_32_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/3-540-48447-7_20","volume-title":"WADS","author":"Lukovszki T.","year":"1999","unstructured":"Lukovszki , T. New results of fault tolerant geometric spanners . In WADS ( 1999 ), F. K. H. A. Dehne, A. Gupta, J.-R. Sack, and R. Tamassia, Eds., vol. 1663 of Lecture Notes in Computer Science , Springer , pp. 193 -- 204 . Lukovszki, T. New results of fault tolerant geometric spanners. In WADS (1999), F. K. H. A. Dehne, A. Gupta, J.-R. Sack, and R. Tamassia, Eds., vol. 1663 of Lecture Notes in Computer Science, Springer, pp. 193--204."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1208237"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833517"},{"key":"e_1_3_2_1_35_1","volume-title":"Notes on binary dumbbell trees","author":"Smid M.","year":"2012","unstructured":"Smid , M. Notes on binary dumbbell trees , 2012 . Smid, M. Notes on binary dumbbell trees, 2012."},{"key":"e_1_3_2_1_36_1","series-title":"CRPIT","first-page":"7","volume-title":"CATS","author":"Smid M. H. M.","year":"2006","unstructured":"Smid , M. H. M. Geometric spanners with few edges and degree five . In CATS ( 2006 ), J. Gudmundsson and C. B. Jay, Eds ., vol. 51 of CRPIT , Australian Computer Society , pp. 7 -- 9 . Smid, M. H. M. Geometric spanners with few edges and degree five. In CATS (2006), J. Gudmundsson and C. B. Jay, Eds., vol. 51 of CRPIT, Australian Computer Society, pp. 7--9."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-5980-0"}],"event":{"name":"SoCG '13: Symposium on Computational Geometry 2013","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rio de Janeiro Brazil","acronym":"SoCG '13"},"container-title":["Proceedings of the twenty-ninth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2462356.2462381","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2462356.2462381","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:29Z","timestamp":1750234709000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2462356.2462381"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,17]]},"references-count":37,"alternative-id":["10.1145\/2462356.2462381","10.1145\/2462356"],"URL":"https:\/\/doi.org\/10.1145\/2462356.2462381","relation":{},"subject":[],"published":{"date-parts":[[2013,6,17]]},"assertion":[{"value":"2013-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}