Triangular embeddings of complete graphs (neighborly maps) with 12 and 13 vertices

In this paper, we describe the generation of all nonorientable triangular embeddings of the complete graphs K 12 and K 13 . (The 59 nonisomorphic orientable triangular embeddings of K 12 were found in 1996 by Altshuler, Bokowski, and Schuchert, and K 13 has no orientable triangular embeddings.) There are 182,200 nonisomorphic nonorientable triangular embeddings for K 12 , and 243,088,286 for K 13 . Triangular embeddings of complete graphs are also known as neighborly maps and are a type of twofold triple system. We also use methods of Wilson to provide an upper bound on the number of simple twofold triple systems of order n , and thereby on the number of triangular embeddings of K n . We mention an application of our results to flexibility of embedded graphs. © 2005 Wiley Periodicals, Inc. J Combin Designs