The solution of the Heawood problem (see [3]) shows that the complete graph K* _{n}*
admits a triangular embedding into some surface whenever the obvious necessary
condition that

If the dual graph of a triangular embedding of K* _{n}* is
bipartite (which is only possible when

**Conjecture 1 (Ellingham and Mohar, November 2002):**
Let S be a Steiner triple system of order *n*. If *n*
is large enough, then S can be extended to a triangular embedding of K* _{n}*
in some nonorientable surface.

By "extending" a STS to an embedding we mean an embedding in which
all blocks of the triple system form facial cycles. Exceptional values of *n*
are 3, 4, and 7 for which only orientable embeddings exist. It is possible that
these are the only exceptions.

If true, Conjecture 2 would imply that for all admissible large values of *n*,
there are at least exp(*n*^{2} log *n* / 6 - o(*n*^{2}))
nonisomorphic triangular embeddings of K* _{n}* in nonorientable surfaces.

**Conjecture 2 (Ellingham and Mohar, November 2002):**
Let S and S' be Steiner triple systems of odd order *n*.
If *n* is large enough, then S and an isomorphic copy of S' form a
triangular embedding of K* _{n}* in some nonorientable surface.

If true, Conjecture 2 would imply that for all admissible large values of *n*,
there are at least exp(*n*^{2} log *n* / 3 - o(*n*^{2}))
nonisomorphic triangular embeddings of K* _{n}* in nonorientable surfaces
such that the dual is bipartite. It is easy to see that this bound would be
asymptotically best
possible. This would also imply that complete graphs may have the biggest
face-width-3 flexibility among all graphs of given genus, a property that has
been conjectured by Neil Robertson (private communication) some time ago; see
also [2].

References:

[1] P. Bonnington, M. Grannell, T. Griggs, and J. Siran, Exponential families of non-isomorphic triangulations of complete graphs, J. Combin. Theory Ser. B 78 (2000) 169-184.

[2] B. Mohar, N. Robertson, Flexibility of polyhedral embeddings of graphs in surfaces, J. Combin. Theory, Ser. B 83 (2001) 38-57.

[3] G. Ringel, Map Color Theorem, Springer-Verlag, Berlin, 1974.

**Some comments added in December 2004:**

Mark Ellingham informed me that [4] contains an upper bound on the number of triangular embeddings of K_{n},
based on ideas by R. M. Wilson, that is (very slightly) better than the obvious upper
bound of (n-2)^{n(n-1)/3}: the improved bound is
(n/e)^{(n^2)/3}.
This appears in [4].

[4] M. Ellingham and C. Stephens, Triangular embeddings of complete graphs (neighborly maps) with 12 and 13 vertices, submitted to the Journal of Combinatorial Designs.

[5] G. K. Bennett, M. J. Grannell and T. S. Griggs, On the bi-embeddability of certain Steiner triple systems of order 15, Europ. J. Combin. 23 (2002) 499-505.

[6] M. J. Grannell, T. S. Griggs and J. Siran, Surface embeddings of Steiner triple systems, J. Combin. Designs 6 (1998) 325-336.

Send comments to Bojan.Mohar@uni-lj.si