On certain Hamiltonian cycles in planar graphs

The problem is considered under which conditions a 4-connected planar or pr ojective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obta in novel lower bounds on the number of distinct Hamiltonian cycles that mus t be present in a 5-connected graph that is embedded into the plane or into the projective plane with face-width at least five. Especially, we show th at every 5-connected plane or projective plane triangulation on n vertices with no non-contractible cycles of length less than five contains at least 2(O)(n(1/4)) distinct Hamiltonian cycles. (C) 1999 John Wiley & Sons, Inc.