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

DOI10.1016/0166-218X(84)90109-4MaRDI QIDQ788489zbMATH OpenOpenAlexFDO

Authors T. Asano, Shunji Kikuchi, Nobuji Saito

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 cycleNP-completeplanar graphlinear time algorithm

Mathematics Subject Classification ID

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

Recommendations

• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Finding Hamiltonian cycles in certain planar graphs
• Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time
• scientific article; zbMATH DE number 4016941

Cites work

• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3630798 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• A Theorem on Planar Graphs
• A method in graph theory
• Efficient Planarity Testing
• Parallel concepts in graph theory
• The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(22)

• Finding and enumerating Hamilton cycles in 4-regular graphs
• On the visibility graph of convex translates
• Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs
• Computing Tutte paths
• A note on Hamiltonian cycles in planar graphs
• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• A new algorithm for embedding plane graphs at fixed vertex locations
• Parameterized algorithms in smooth 4-regular Hamiltonian graphs
• A data structure useful for finding Hamiltonian cycles
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• Hamiltonian properties of polyhedra with few 3-cuts. A survey
• scientific article; zbMATH DE number 2077653 (Why is no real title available?)
• Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time
• Graph theory (algorithmic, algebraic, and metric problems)
• Finding Hamiltonian cycles in certain planar graphs
• scientific article; zbMATH DE number 7561516 (Why is no real title available?)
• An extension of Whitney's theorem to infinite strong triangulations
• The visibility graph of congruent discs is Hamiltonian
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• Connectivity of plane triangulations
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q788489)