The problem of determining a minimal spanning tree has interesting spinoffs when the vertices of the graph are points in a metric space (usualy Rn), and the resource being minimized is distance. As always, the greedy algorithm provides a minimal spanning tree in polynomial time. However, additional points, strategically placed, sometimes allow the original set of points to be connected using less overall edge length. Example: the minimal spanning tree connecting the three vertices of a unit equilateral triangle has length 2. By adding a point in the middle (equidistant from the original three), we can connect the three vertices using only sqrt(3) units of edge length. This is obviously less than 2; an improvement.
An additional point that reduces the length of the spanning tree is called a steiner point. The resulting tree is called a steiner tree. A minimal steiner tree minimizes total edge length. The minimum steiner tree is the best possible steiner tree. Finding such a tree can be very difficult.
A steiner point cannot be an endpoint, else we could simply delete it and its associated edge, reducing the length of the spanning tree. By the triangular inequality, a steiner point cannot have degree two.
Let the steiner point have degree 3, while the graph lives in normal space. If the point is "out of plane", move the steiner point into the plane determined by the three adjacent points, reducing the lengths of all the incident edges. Then suppose one of the three angles is less than 120°. Move the point a distance δ down the angle bisector, thus opening the angle up. The two lines supporting this angle each decrease by at least half of δ, while the third line increases by at most δ. The sum of the three lengths has decreased. In a minimal steiner tree, the steiner points of degree 3 all have angles of 120°, and are "in plane". Note that a steiner point cannot meaningfully connect three points that form a triangle whose obtuse angle exceeds 120°.
If a vertex has degree 4 or more, find to edges that form an angle less than 120°, and slide a new steiner point away from the high degree vertex, down the angle bisector. As before, the angle lines shorten while the new steiner line lengthens. The other lines coming into the vertex do not move or change. Continue spawning new steiner points until each steiner point has degree 3, and each of the original vertices has degree 3 or less.
Let's connect the corners of a unit square. Without steiner points, the spanning tree has length 3, with 3 of the 4 sides drawn in. Your next impulse is to connect the four corners to the center, introducing one steiner point. This gives an edge length of 2.828, a definite improvement over 3. Next, split the steiner point in two and pull the two points apart, towards the left and right sides of the square, until the angles are 120°. This gives an edge length of 2.732. This is the best steiner tree for the square.
We can always do this because four lines imply at least one angle of 109° or less, and more incident edges can only introduce smaller angles. So a new point can always pull away, and open up the angle to 120°.