| Abstract: | We consider vertex-transitive graphs embeddable on a fixed surface. We prove that all but a finite number of them admit embeddings as vertex-transitive maps on surfaces of nonnegative Euler characteristic (sphere, projective plane, torus, or Klein bottle). It follows that with the exception of the cycles and a finite number of additional graphs, they are factor graphs of semiregular plane tilings. The results generalize previous work on the genus of minimal Cayley graphs by V. Proulx and T. W. Tucker and were obtained independently by C. Thomassen, with significant differences in the methods used. Our method is based on an excursion into the infinite. The local structure of our finite graphs is studied via a pointwise limit construction, and the infinite vertex-transitive graphs obtained as such limits are classified by their connectivity and the number of ends. In two appendices, we derive a combinatorial version of Hurwitz's Theorem, and classify the vertex-transitive maps on the Klein bottle. |
