Shortest enclosing walks and cycles in embedded graphs (Q1116348)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4088948
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Shortest enclosing walks and cycles in embedded graphs |
scientific article; zbMATH DE number 4088948 |
Statements
Shortest enclosing walks and cycles in embedded graphs (English)
0 references
1989
0 references
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.
0 references
enclosing walk
0 references
enclosing cycle
0 references
embedded graph
0 references
plane graph
0 references
0.831244707107544
0 references
0.7979528903961182
0 references
0.7979527711868286
0 references
0.7806889414787292
0 references
0.7670497298240662
0 references
