On Hamilton cycles in certain planar graphs

DOI<43::AID-JGT6>3.0.CO;2-M 10.1002/(SICI)1097-0118(199601)21:1<43::AID-JGT6>3.0.CO;2-MzbMath0839.05068OpenAlexW4251672073MaRDI QIDQ4862107

Daniel P. Sanders

Publication date: 5 June 1996

Full work available at URL: https://doi.org/10.1002/(sici)1097-0118(199601)21:1<43::aid-jgt6>3.0.co;2-m

zbMATH Keywords

Hamiltonian cycleplanar graphplane graphchordplanar triangulationslinear algorithmcut-setWhitney's theoremboundary graphouter facechordal facetheorem of Tutte

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45)

Related Items

Every 4-Connected Graph with Crossing Number 2 is Hamiltonian ⋮ Computing Tutte Paths ⋮ On 2-connected spanning subgraphs with low maximum degree ⋮ Hamiltonian cycles and 1-factors in 5-regular graphs ⋮ Bounding tree-width via contraction on the projective plane and torus ⋮ Find subtrees of specified weight and cycles of specified length in linear time ⋮ On the hamiltonicity of a planar graph and its vertex‐deleted subgraphs ⋮ K₂‐Hamiltonian graphs: II ⋮ Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey ⋮ Structural properties for certain classes of infinite planar graphs ⋮ Fast minor testing in planar graphs ⋮ 2-edge-Hamiltonian-connectedness of 4-connected plane graphs ⋮ Long cycles in 4-connected planar graphs ⋮ 4-connected polyhedra have at least a linear number of Hamiltonian cycles ⋮ Cycle spectra of contraction-critically 4-connected planar graphs ⋮ Book Embedding of Graphs on the Projective Plane ⋮ On Hamiltonian cycles in 4- and 5-connected plane triangulations ⋮ $K_2$-Hamiltonian Graphs: I ⋮ Surfaces, tree-width, clique-minors, and partitions ⋮ Distribution of subtree sums