On Embeddings of Circulant Graphs

A circulant of order n is a Cayley graph for the cyclic group ℤn, and as such, admits a transitive action of ℤn on its vertices. This paper concerns 2-cell embeddings of connected circulants on closed orientable surfaces. Embeddings on the sphere (the planar case) were classified by Heuberger (2003), and by a theorem of Thomassen (1991), there are only finitely many vertex-transitive graphs with minimum genus g, for any given integer g ≥ 3. Here we completely determine all connected circulants with minimum genus 1 or 2; this corrects and extends an attempted classification of all toroidal circulants by Costa, Strapasson, Alves and Carlos (2010).