Optimal enclosing regions in planar graphs
Daniel A. Bienstock, Clyde L. Monma · Networks · 1989
Abstract In this paper we study the problem of finding a minimum‐weight collection of edges in a planar graph which separates a given set of vertices from the outer face. This problem has two variants: either a given embedding is specified, or the best possible embedding is to be found. We present polynomial‐time algorithms for each case. We show how to use these results to recognize a special case of the steiner tree problem in graphs which is polynomially solvable. A closely related problem is shown to be NP ‐complete.