A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
DOI10.1016/0166-218X(84)90109-4zbMATH Open0531.68008OpenAlexW2057568938MaRDI QIDQ788489FDOQ788489
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
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient Planarity Testing
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Parallel concepts in graph theory
- A Theorem on Planar Graphs
- Title not available (Why is that?)
- A method in graph theory
- The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
- Title not available (Why is that?)
Cited In (22)
- On the visibility graph of convex translates
- Finding and enumerating Hamilton cycles in 4-regular graphs
- Computing Tutte paths
- Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs
- 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
- Title not available (Why is that?)
- Finding Hamiltonian cycles of truncated rectangular grid graphs in linear time
- Hamiltonian properties of polyhedra with few 3-cuts. A survey
- Graph theory (algorithmic, algebraic, and metric problems)
- Title not available (Why is that?)
- Finding Hamiltonian cycles in certain planar graphs
- 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
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
- Connectivity of plane triangulations
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)
