Computing the degree-4 shortest network under a given topology

Let F be a set of n (n being an even number) fixed points and let M be a set of n/2-1 moving points, whose locations are to be determined, in the plane. A topology is a set of edges connecting these points in the set V = F ∪ M. Let E be a full 4-degree Steiner topology; i.e., the topology forms a tree which contains fixed points of degree 1 and moving points of degree 4, and let H (E) be a set of topologies which include E and its degeneracies. We define a canonical tree over V as one whose topology belongs to H (E) and in which the sum of two adjacent angles around any node is not less than π. In this paper we prove that if a canonical tree exists, then it is the shortest (degree-4) network under a given topology E. We present an O (n²) time algorithm for finding a degree-4 shortest network whose topology belongs to H (E).