A characterization of regular embeddings of nn-dimensional cubes

One of the central problems in topological graph theory is the problem of the classification of graph embeddings into surfaces exhibiting a maximum number of symmetries. These embeddings are called regular. In particular, Du, Kwak and Nedela (2005) classified regular embeddings of nn-dimensional cubes QnQn for nn odd. For even nn Kwon has constructed a large family of regular embeddings with an exponential growth with respect to nn. The classification was recently extended by J. Xu to numbers n=2mn=2m, where mm is odd by showing that these embeddings coincide with the embeddings constructed by Kwon (2004) [21].In the present paper we give a characterization of regular embeddings of QnQn. We employ it to derive structural results on the automorphism groups of such embeddings as well as to construct a family of embeddings not covered by the Kwon embeddings.