Given a graph G cellularly embedded in a closed surface S, an automorphism of G is called a “cellular automorphism of G in S” when, loosely speaking, it takes facial boundary walks to facial boundary walks. I will describe how Dan Slilaty and I constructed complete catalogs of all irreducible cellular automorphisms of the sphere, projective plane, torus, Klein bottle, and three-crosscap surface for a particular notion of reducibility related to taking minors.

We have also determined concrete procedures sufficient for constructing all possible self-dual embeddings in any closed surface S given a catalog of all irreducible cellular automorphisms in S.

I will illustrate by way of examples some of these procedures and some resulting self-dual graphs.

This talk is based on joint work with Dan Slilaty.