Shortest enclosing walks and cycles in embedded graphs (Q1116348)

We consider the problem of finding a shortest closed walk (SEW) or cycle (SEC) surrounding a given obstacle O in the plane and chosen from a nonnegatively weighted graph G with a fixed (not necessarily planar) embedding in the plane. We show that SEW is polynomial if O is connected and NP-hard otherwise, that SEC is polynomial when O is a topological ball and NP-hard if O is a general connected region, and that both SEW and SEC are polynomial for general O when G has a plane layout.