Shortest enclosing walks and cycles in embedded graphs

DOI10.1016/0020-0190(89)90129-4zbMath0665.68054OpenAlexW1976021853MaRDI QIDQ1116348

J. Scott Provan

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90129-4

zbMATH Keywords

plane graphembedded graphenclosing cycleenclosing walk

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (5)

On finding two-connected subgraphs in planar graphs ⋮ The role of Steiner hulls in the solution to Steiner tree problems ⋮ Automatic deformation of Riemann-Hilbert problems with applications to the Painlevé II transcendents ⋮ Two new criteria for finding Steiner hulls in Steiner tree problems ⋮ Minimal connected enclosures on an embedded planar graph

Cites Work

• Unnamed Item
• Unnamed Item
• Convexity and the Steiner tree problem
• An Approximation Scheme for Finding Steiner Trees with Obstacles
• Optimal enclosing regions in planar graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

This page was built for publication: Shortest enclosing walks and cycles in embedded graphs