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.