On the structure and complexity of the 2-connected Steiner network problem in the plane

We consider the problem of finding a minimum Euclidean length graph 2-connecting a set of points in the plane. We show that the solution to this problem is an edge-disjoint union of full Steiner trees. This has three important corollaries. The first is a proof that the problem is NP-hard, even in the sense of finding a fully polynomial approximation scheme. The second is a complete description of the solutions for 2SNPP for rectangular arrays of lattice points. The third is a linear-time algorithm for constructing an optimal solution to 2SNPP given its topological description.