Robust geometric spanners

Pat Morin

We consider a new definition of fault-tolerance for geometric t-spanners that we call robustness. A t-spanner is f(k)-robust if the removal of any k vertices leaves a set of n-f(k) vertices that are unaffected, i.e., there still remains a t-spanning path between every pair of vertices in this set.

We prove that f(k)-robust spanners have a superlinear number of edges, even in one dimension. On the positive side, we give constructions of t-spanners having a near-linear number of edges that are f(k)-robust.