Minimal connected enclosures on an embedded planar graph

We study five problems of finding minimal enclosures comprised of elements of a connected, planar graph with a plane embedding. The first three proble ms consider the identification of a shortest enclosing walk, cycle or trail surrounding a polygonal, simply connected obstacle on the plane. We propos e polynomial algorithms that improve on existing algorithms. The last two p roblems consider the formation of minimal zones (sets of adjacent regions s uch that any pair of points in a zone can be connected by a non-zero width curve that lies entirely in the zone). Specifically, we assume that the reg ions of the graph have nonnegative weights and seek the formation of minimu m weight zones containing a set of points or a set of regions. We prove tha t the last two problems are NP-hard and transform them to Steiner arboresce nce/fixed-charge flow problems. (C) 1999 Published by Elsevier Science B.V. All rights reserved.