Robust Geometric Spanners

Details Robust Geometric Spanners Robust Geometric Spanners

2012-04-20

arxiv.org/abs/1204.4679v1

Computer Science

Computational Geometry

18 pages, 8 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Robust Geometric Spanners does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Robust Geometric Spanners, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust Geometric Spanners will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-6099