On Euclidean spanner graphs with small degree
Jeffrey S. Salowe · 1992
Given a set of points S, a t-spanner for S is a subgraph G of the complete Euclidean graph determined by S having the property that dG(x,y)/d(x,y) ≤ t for all x,y e S, x ≠ y, where dG(x, y) is the distance from point x is the euclidean distance from x to y. Dobkin, Friedman, and Supowit posed the problem of determining whether every planar point set S admits a t-spanner having maximum vertex degree 3 for some constant t. We show that for each k ≥ 2, there is a constant t(k) such that every point set in Rk admits a t(k)-spanner with vertex degree at most 4.