Dihedral biembeddings and triangulations by complete and complete tripartite graphs

Grannell, M. J. and Knor, M. (2013). Dihedral biembeddings and triangulations by complete and complete tripartite graphs. Graphs and Combinatorics, 29(4) pp. 921–932.

DOI: https://doi.org/10.1007/s00373-012-1163-1

URL: http://link.springer.com/article/10.1007/s00373-01...

Abstract

We construct biembeddings of some Latin squares which are Cayley tables of dihedral groups. These facilitate the construction of $n^{an^2}$ nonisomorphic face 2-colourable triangular embeddings of the complete tripartite graph $K_{n,n,n}$ and the complete graph $K_n$ for linear classes of values of $n$ and suitable constants $a$ . Previously the best known lower bounds for the number of such embeddings that are applicable to linear classes of values of $n$ were of the form $2^{an^2}$ . We remark that trivial upper bounds are $n^{n^2/3}$ in the case of complete graphs $K_n$ and $n^{2n^2}$ in the case of complete tripartite graphs $K_{n,n,n}$ .