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. Copyright 2013 ACM.

Additional Metadata
Keywords Fault-tolerance, Geometric spanners, High treewidth
Conference 29th Annual Symposium on Computational Geometry, SoCG 2013
Citation
Bose, P, Dujmović, V, Morin, P, & Smid, M. (2013). Robust geometric spanners. Presented at the 29th Annual Symposium on Computational Geometry, SoCG 2013.