Finding a noncrossing Steiner forest in plane graphs under a 2-face condition

Let G = (V, E) be a plane graph with nonnegative edge weights, and let N be a family of k vertex sets N-1, N-2, ...,N-k subset of or equal to V, calle d nets. Then a noncrossing Steiner forest for N in G is a set T of k trees T-1,T-2, ...,T-k in G such that each tree T-i is an element of T connects a ll vertices, called terminals, in net N-i, any two trees in T do not cross each other, and the sum of edge weights of all trees is minimum. In this pa per we give an algorithm to find a noncrossing Steiner forest in a plane gr aph G for the case where all terminals in nets lie on any two of the face b oundaries of G. The algorithm takes time O(n log n) if G has n vertices and each net contains a bounded number of terminals.