Hamiltonian embeddings from triangulations

A Hamiltonian embedding of K_n is an embedding of K_n in a surface,which may be orientable or non-orientable, in such a way thatthe boundary of each face is a Hamiltonian cycle. Ellinghamand Stephens recently established the existence of such embeddingsin non-orientable surfaces for n = 4 and n 6. Here we presentan entirely new construction which produces Hamiltonian embeddingsof K_n from triangulations of K_n when n 0 or 1 (mod 3). We thenuse this construction to obtain exponential lower bounds forthe numbers of nonisomorphic Hamiltonian embeddings of K_n.