  A graph $G$ covers a graph $H$ if there exists a locally bijective
homomorphism from $G$ to $H$. We deal with regular covers in which this locally
bijective homomorphism is prescribed by an action of a subgroup of ${\rm
Aut}(G)$. Regular covers have many applications in constructions and studies of
big objects all over mathematics and computer science.
  We study computational aspects of regular covers that have not been addressed
before. The decision problem RegularCover asks for two given graphs $G$ and $H$
whether $G$ regularly covers $H$. When $|H|=1$, this problem becomes Cayley
graph recognition for which the complexity is still unresolved. Another special
case arises for $|G| = |H|$ when it becomes the graph isomorphism problem.
Therefore, we restrict ourselves to graph classes with polynomially solvable
graph isomorphism.
  Inspired by Negami, we apply the structural results used by Babai in the
1970's to study automorphism groups of graphs. Our main result is the following
FPT meta-algorithm: Let $\cal C$ be a class of graphs such that the structure
of automorphism groups of 3-connected graphs in $\cal C$ is simple. Then we can
solve RegularCover for $\cal C$-inputs $G$ in time $O^*(2^{e(H)/2})$ where
$e(H)$ denotes the number of the edges of $H$. As one example of $\cal C$, this
meta-algorithm applies to planar graphs. In comparison, testing general graph
covers is known to be NP-complete for planar inputs $G$ even for small fixed
graphs $H$ such as $K_4$ or $K_5$. Most of our results also apply to general
graphs, in particular the complete structural understanding of regular covers
for 2-cuts.
