Spanning trees and spanners

David Eppstein
Handbook of Computational Geometry, J�rg-Rudiger Sack and Jorge Urrutia, ed., Elsevier, 2000, pp. 425–461
Tech. report 96-16, Univ. of California, Irvine, Dept. of Information and Computer Science, 1996
http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf

Cited by:

Progress in Hierarchical Clustering & Minimum Weight Triangulation
Exploiting domain geometry in analogical route planning
Partitioned neighborhood spanners of minimal outdegree
Geometric shortest paths and network optimization
Spanners in $l_1$
Experiments with computing geometric minimum spanning trees
Approximation algorithms for the bottleneck stretch factor problem
Approximating the stretch factor of Euclidean graphs
Geometric spanner for routing in mobile networks
Constructing plane spanners of bounded degree and low weight
Sublinear time approximation of Euclidean minimum spanning tree
Practical construction of metric $t$-spanners
Euclidean bounded-degree spanning tree ratios
Fault-tolerant geometric spanners
Approximating geometric bottleneck shortest paths
Tree-approximations for the weighted Cost-Distance problem
On the spanning ratio of Gabriel graphs and beta-skeletons
Extreme distances in multicolored point sets
Optimal spanners for axis-aligned rectangles
Geometric dilation of closed planar curves: a new lower bound
Spatiotemporal multicast in sensor networks
On local algorithms for topology control and routing in ad hoc networks
Topology control and routing in ad hoc networks: a survey
Estimating the weight of metric minimum spanning trees in sublinear-time
Design and analysis of spatiotemporal multicast protocols for wireless sensor networks
On greedy geographic routing algorithms in sensing-covered networks
Computing the maximum detour and spanning ratio of planar paths, trees and cycles
The visibility graph contains a bounded degree spanner
Deformable spanners and applications
On the geometric dilation of curves and point sets
Construction of minimum-weight spanners
Finding the best shortcut in a geometric network
The minimum-area spanning tree problem
Many distances in planar graphs
Approximation algorithms for embedding general metrics into trees
Region-fault tolerant geometric spanners