The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs

DOI10.1016/0196-6774(89)90012-6zbMath0689.68089OpenAlexW1983755786WikidataQ56138404 ScholiaQ56138404MaRDI QIDQ3031944

Norishige Chiba, Takao Nishizeki

Publication date: 1989

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(89)90012-6

zbMATH Keywords

NP-completenessHamiltonian cycle problem

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)

Related Items (30)

Guarding rectangular art galleries ⋮ On \(k\)-greedy routing algorithms ⋮ On certain Hamiltonian inner triangulations ⋮ Two-page book embeddings of 4-planar graphs ⋮ A survey on book-embedding of planar graphs ⋮ Graph-theoretical conditions for inscribability and Delaunay realizability ⋮ 5-Connected Toroidal Graphs are Hamiltonian-Connected ⋮ Unnamed Item ⋮ Computing Tutte Paths ⋮ Circumscribing polygons and polygonizations for disjoint line segments ⋮ Find subtrees of specified weight and cycles of specified length in linear time ⋮ A note on Hamiltonian cycles in planar graphs ⋮ Arc diagrams, flip distances, and Hamiltonian triangulations ⋮ Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey ⋮ Connectivity of plane triangulations ⋮ Finding Hamiltonian cycles in certain planar graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Problems on pairs of trees and the four colour problem of planar graphs ⋮ Guthrie's problem: new equivalences and rapid reductions ⋮ Hamiltonian triangulations and circumscribing polygons of disjoint line segments ⋮ Unnamed Item ⋮ Curve-constrained drawings of planar graphs ⋮ Unnamed Item ⋮ Hamiltonian properties of polyhedra with few 3-cuts. A survey ⋮ Universal hinge patterns for folding strips efficiently into any grid polyhedron ⋮ Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs ⋮ AN ALGORITHM FOR FINDING LONGEST CYCLES IN CERTAIN BIPARTITE GRAPHS ⋮ 4-connected projective-planar graphs are Hamiltonian-connected ⋮ Chinese remainder encoding for Hamiltonian cycles

This page was built for publication: The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs