On Shortest 2-Connected Steiner Networks on 6 and
Points in the Plane

Shuying Peng, Shenggui Zhang and T.C. Edwin Cheng
Department of Applied Mathematics, Northwestern Polytechnical University,
Xi'an, Shaanxi 710072,
P.R.China

Abstract    
We consider the problem of finding a shortest 2-connected Steiner network connecting a set of points in the plane. In this paper, we are mainly concerned with a conjecture of Winter and Zachariasen which states that shortest 2-connected Steiner networks on 6 and 7 points in the plane contain no Steiner points. After reviewing some of the known results for the problem, we give a sufficient condition for a shortest 2-connected Steiner network to be basic and that for two vertices of degree three being nonadjacent in a shortest 2-connected Steiner network. Then, we establish upper bounds for the number of Steiner points in shortest 2-connected Steiner networks on 6 and 7 points. Based on these results, we prove that a shortest 2-connected Steiner networks on 6 and 7 points is either a shortest 2-connected spanning network or isomorphic to several specific networks.