Shortest enclosing walks and cycles in embedded graphs
type: Item
instance of: scholarly article
title: Shortest enclosing walks and cycles in embedded graphs
zbMATH Open document ID: 0665.68054
DOI: 10.1016/0020-0190(89)90129-4
author: J. Scott Provan
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4088948
zbMATH Keywords: enclosing walk
zbMATH Keywords: enclosing cycle
zbMATH Keywords: embedded graph
zbMATH Keywords: plane graph
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90129-4
OpenAlex ID: W1976021853
cites work: Q5535091
cites work: Optimal enclosing regions in planar graphs
cites work: The complexity of theorem-proving procedures
cites work: Fibonacci heaps and their uses in improved network optimization algorithms
cites work: Q5557005
cites work: Convexity and the Steiner tree problem
cites work: An Approximation Scheme for Finding Steiner Trees with Obstacles
cites work: The complexity of satisfiability problems
description: scientific article; zbMATH DE number 4088948