ON HAMILTON CYCLES IN CERTAIN PLANAR GRAPHS

Let G be a 2-connected plane graph with outer cycle X(G) such that for every minimal vertex cut S of G with ISI less than or equal to 3, eve ry component of G\S contains a vertex of X(G). A sufficient condition for G to be Hamiltonian is presented. This theorem generalizes both Tu tte's theorem that every 4-connected planar graph is Hamiltonian, as w ell as a recent theorem of Dillencourt about NST-triangulations. A lin ear algorithm to find a Hamilton cycle can be extracted from the proof . One corollary is that a 4-connected planar graph with the vertices o f a triangle deleted is Hamiltonian. (C) 1996 John Wiley & Sons, Inc.