There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees

Let S be a set ofn points in the plane. For an arbitrary positive rationalr, we construct a planar straight-line graph onS that approximates the complete Euclidean graph onS within the factor (1 + 1/r)2/3 cos(/6)], and it has length bounded by 2r + 1 times the length of a minimum Euclidean spanning tree onS. Given the Deiaunay triangulation ofS, the graph can be constructed in linear time.