The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
From MaRDI portal
Publication:3947135
DOI10.1137/0211042zbMath0486.68061MaRDI QIDQ3947135
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211042
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
05C45: Eulerian and Hamiltonian graphs
Related Items
A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs, Connectivity of plane triangulations, Combinatorial analysis (nonnegative matrices, algorithmic problems), Finding Hamiltonian circuits in interval graphs, A unified approach to visibility representations of planar graphs, Hamiltonian circuits in interval graph generalizations, Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete