A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs

DOI10.1016/0166-218X(84)90109-4zbMath0531.68008OpenAlexW2057568938MaRDI QIDQ788489

Shunji Kikuchi, Nobuji Saito, Takao Asano

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(84)90109-4

zbMATH Keywords

Hamiltonian cyclelinear time algorithmNP-completeplanar graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Related Items (11)

The visibility graph of congruent discs is Hamiltonian ⋮ A new algorithm for embedding plane graphs at fixed vertex locations ⋮ An extension of Whitney's theorem to infinite strong triangulations ⋮ Computing Tutte Paths ⋮ Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey ⋮ Connectivity of plane triangulations ⋮ Hamiltonian triangulations and circumscribing polygons of disjoint line segments ⋮ On the visibility graph of convex translates ⋮ Unnamed Item ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Hamiltonian properties of polyhedra with few 3-cuts. A survey

Cites Work

• A method in graph theory
• Parallel concepts in graph theory
• A Theorem on Planar Graphs
• The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
• Efficient Planarity Testing
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs