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

DOI10.1137/0211042MaRDI QIDQ3947135zbMATH OpenOpenAlexFDO

Authors 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

bridge, planted plane treeNP-complete

Mathematics Subject Classification ID

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

Cited in

(12)

• A linear time recognition algorithm for proper interval graphs
• 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
• Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey
• Computing Tutte paths
• Connected proper interval graphs and the guard problem in spiral polygons (extended abstract)
• Hamiltonian path in permutation graphs
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• Connectivity of plane triangulations

This page was built for publication: The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3947135)