3-connected Reduction for Regular Graph Covers
Jiří Fiala, Pavel Klavík, Jan Kratochvíl, Roman Nedela
A graph $G$ covers a graph $H$ if there exists a locally bijective
homomorphism from $G$ to $H$. We deal with regular coverings in which this
homomorphism is prescribed by an action of a semiregular subgroup $\Gamma$ of
$\textrm{Aut}(G)$; so $H \cong G / \Gamma$. In this paper, we study the
behaviour of regular graph covering with respect to 1-cuts and 2-cuts in $G$.
We describe reductions which produce a series of graphs $G = G_0,\dots,G_r$
such that $G_{i+1}$ is created from $G_i$ by replacing certain inclusion
minimal subgraphs with colored edges. The process ends with a primitive graph
$G_r$ which is either 3-connected, or a cycle, or $K_2$. This reduction can be
viewed as a non-trivial modification of reductions of Mac Lane (1937),
Trachtenbrot (1958), Tutte (1966), Hopcroft and Tarjan (1973), Cuningham and
Edmonds (1980), Walsh (1982), and others. A novel feature of our approach is
that in each step all essential information about symmetries of $G$ are
preserved.
A regular covering projection $G_0\to H_0$ induces regular covering
projections $G_i \to H_i$ where $H_i$ is the $i$-th quotient reduction of
$H_0$. This property allows to construct all possible quotients $H_0$ of $G_0$
from the possible quotients $H_r$ of $G_r$. By applying this method to planar
graphs, we give a proof of Negami's Theorem (1988). Our structural results are
also used in subsequent papers for regular covering testing when $G$ is a
planar graph and for an inductive characterization of the automorphism groups
of planar graphs (see Babai (1973) as well).