×

zbMATH — the first resource for mathematics

4-connected projective planar graphs are Hamiltonian. (English) Zbl 0802.05051
We prove the result stated in the title (conjectured by Grünbaum) and a conjecture of Plummer that every graph which can be obtained from a 4- connected planar graph by deleting two vertices is Hamiltonian. The proofs are constructive and give rise to polynomial-time algorithms.

MSC:
05C45 Eulerian and Hamiltonian graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI