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.