The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs

DOI10.1137/0211042zbMath0486.68061OpenAlexW1975729263MaRDI QIDQ3947135

Dominique Gouyou-Beauchamps

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

zbMATH Keywords

NP-completebridge, planted plane tree

Mathematics Subject Classification ID

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

Related Items

A unified approach to visibility representations of planar graphs, Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete, Hamiltonian circuits in interval graph generalizations, Computing Tutte Paths, Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey, Connectivity of plane triangulations, A linear time recognition algorithm for proper interval graphs, A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs, Combinatorial analysis (nonnegative matrices, algorithmic problems), Finding Hamiltonian circuits in interval graphs