A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
DOI10.1016/0166-218X(84)90109-4zbMATH Open0531.68008OpenAlexW2057568938MaRDI QIDQ788489FDOQ788489
Shunji Kikuchi, Nobuji Saito, T. 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
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
- Efficient Planarity Testing
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Parallel concepts in graph theory
- A Theorem on Planar Graphs
- A method in graph theory
- The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (15)
- 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
- 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
- Hamiltonian properties of polyhedra with few 3-cuts. A survey
- Graph theory (algorithmic, algebraic, and metric problems)
- Title not available (Why is that?)
- 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
- 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)
