A characterization of regular embeddings of n-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 n-dimensional cubes Q(n) for n odd. For even n Kwon has constructed a large family of regular embeddings with an exponential growth with respect to n. The classification was recently extended by J. Xu to numbers n = 2m. where m 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 Q. 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. (C) 2010 Elsevier B.V. All rights reserved.