Simple algorithms for Steiner trees and paths packing problems in planar graphs

email wagnermathtuberlinde In this paper we give a short survey on ecient algorithms for Steiner trees and paths packing problems in planar graphs We particularly concentrate on recent results The rst result is a lineartime algorithm for packing vertexdisjoint trees resp paths within a planar graph where the vertices to be connected lie on at most two dierent faces This algorithm is based on a lineartime algorithm for the vertexdisjoint Menger problem in planar graphs The second result is a lineartime algorithm for packing edgedisjoint paths within a planar graph where the vertices to be connected all lie on the boundary of the same face All algorithms discussed in detail in this paper admit a short and simple description and are easy to implemen