{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T18:47:04Z","timestamp":1790189224347,"version":"4.1.0"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>Highly connected and yet sparse graphs (such as expanders or graphs of high treewidth) are fundamental, widely applicable, and extensively studied combinatorial objects. We initiate the study of such highly connected graphs that are, in addition, geometric spanners. We define a property of spanners called robustness. Informally, when one removes a few vertices from a robust spanner, this harms only a small number of other vertices. We show that robust spanners must have a superlinear number of edges, even in one dimension. On the positive side, we give constructions, for any dimension, of robust spanners with a near-linear number of edges.<\/jats:p>","DOI":"10.1137\/120874473","type":"journal-article","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T10:47:37Z","timestamp":1376563657000},"page":"1720-1736","source":"Crossref","is-referenced-by-count":4,"title":["Robust Geometric Spanners"],"prefix":"10.1137","volume":"42","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vida","family":"Dujmovi\u0107","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,8,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9343-y"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9137-7"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.01.008"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-011-0346-7"},{"key":"atypb5","first-page":"514","author":"Arikati S. R.","year":"1996","journal-title":"New York"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.07.004"},{"key":"atypb7","first-page":"489","author":"Arya S.","year":"1995","journal-title":"New York"},{"key":"atypb8","first-page":"703","author":"Arya S.","year":"1994","journal-title":"IEEE Computer Society"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00014-0"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523237"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"atypb12","first-page":"11","author":"Bodlaender H. L.","year":"2007","journal-title":"New York"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.04.003"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9293-4"},{"key":"atypb15","first-page":"85","author":"Bose P.","year":"2012","journal-title":"New York"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1168-8"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195909002861"},{"key":"atypb18","unstructured":"P. Carmi and L. Chaitman,\n                      Bounded degree planar geometric spanners\n                      , arXiv:1003.4963, 2010."},{"key":"atypb19","unstructured":"P. Carmi and L. Chaitman,\n                      Stable roommates and geometric spanners\n                      , in Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010, pp. 31-34."},{"key":"atypb20","first-page":"316","author":"Carmi P.","year":"2010","journal-title":"New York"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90044-5"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1121-7"},{"key":"atypb23","first-page":"168","author":"Das G.","year":"1989","journal-title":"New York"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195997000193"},{"key":"atypb25","first-page":"425","author":"Eppstein D.","year":"1999","journal-title":"New York"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"atypb28","first-page":"387","author":"Kalai G.","year":"1991","journal-title":"RI"},{"key":"atypb29","first-page":"47","author":"Keil J. M.","year":"1989","journal-title":"New York"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"T. Kloks,\n                      Treewidth: Computations and Approximations\n                      , Lecture Notes in Comput. Sci. 842, Springer-Verlag, New York, 1994.","DOI":"10.1007\/BFb0045375"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0075-x"},{"key":"atypb32","first-page":"193","author":"Lukovszki T.","year":"1999","journal-title":"New York"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"G. Narasimhan and M. H. M. Smid,\n                      Geometric Spanner Networks\n                      , Cambridge University Press, Cambridge, 2007.","DOI":"10.1017\/CBO9780511546884"},{"key":"atypb34","first-page":"6","author":"Segal M.","year":"2010","journal-title":"INFOCOM, IEEE"},{"key":"atypb35","unstructured":"M. Smid,\n                      Notes on Binary Dumbbell Trees\n                      , Carleton University, Ottawa, Ontario, Canada, 2012."},{"key":"atypb36","first-page":"7","author":"M. H.","year":"2006","journal-title":"Australian Computer Society"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-5980-0"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120874473","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:12:34Z","timestamp":1787339554000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120874473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/120874473"],"URL":"https:\/\/doi.org\/10.1137\/120874473","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}