Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs

Abstract

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 Aut(G).

We apply the structural results used by Babai to study automorphism groups of graphs. Our main result is an FPT algorithm solving RegularCover for planar input G in asymptotic time exp(e(H)/2)) where e(H) denotes the number of the edges of H.

Keywords

• Regular Graph Covers
• Planar Graphs