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\cup 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(n2) time algorithm for finding a degree-4 shortest network whose topology belongs to H(E) .