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

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) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cited in

(12)

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

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)