Graham's problem on shortest networks for points on a circle

Abstract

Suppose a configuration X consists of n points lying on a circle of radius r. If at most one of the edges joining neighboring points has length strictly greater than r, then the Steiner tree S consists of all these edges with a longest edge removed. In order to show S is, in fact, just the minimal spanning tree T, a variational approach is used to show the Steiner ratio for this configuration is at least one and equals one only if S and T coincide. The variational approach greatly reduces the number of possible Steiner trees that need to be considered. © 1992 Springer-Verlag New York Inc.