Polynomially solvable special cases of the Steiner problem in planar networks

The authors give polynomial-time algorithms for two special cases of the Steiner problem: (1)the underlying network is planar and all terminals lie within a bounded number of ‘layers’ of a single face, and (2)the problem is the rectilinear Steiner problem and the number of rectilinear convex hulls in the entire ‘onion’ of convex hulls is bounded. The present algorithms build on well-known dynamic programming algorithms. For the second problem, the authors also use some geometric arguments.