  By a map we mean a $2$-cell decomposition of a closed compact surface, i.e.,
an embedding of a graph such that every face is homeomorphic to an open disc.
Automorphism of a map can be thought of as a permutation of the vertices which
preserves the vertex-edge-face incidences in the embedding. When the underlying
surface is orientable, every automorphism of a map determines an
angle-preserving homeomorphism of the surface. While it is conjectured that
there is no "truly subquadratic" algorithm for testing map isomorphism for
unconstrained genus, we present a linear-time algorithm for computing the
generators of the automorphism group of a map, parametrized by the genus of the
underlying surface. The algorithm applies a sequence of local reductions and
produces a uniform map, while preserving the automorphism group. The
automorphism group of the original map can be reconstructed from the
automorphism group of the uniform map in linear time. We also extend the
algorithm to non-orientable surfaces by making use of the antipodal
double-cover.
