Automorphisms and Isomorphisms of Maps in Linear Time

The graph isomorphism problem asks whether or not two given graphs are isomorphic. It is one of the most fundamental problems in the theory of algorithms. Its computational complexity is still a huge open question, even after Babai's recent quasipolynomial-time breakthrough [4]. While some complexity-theoretic results indicate that this problem is unlikely NP-complete (if it was, the polynomial hierarchy would collapse to its second level, see [31]), no polynomial-time algorithm is known, even with extended resources like randomization or quantum computing. For quite a long time, it has been known that the isomorphism of bounded genus graphs can be solved in time \(n^{{\mathcal{O}}(g)}\), where \(g\) is the genus of the underlying surface; see, for example [30]. An algorithm with running time \(n^{(\log{g})^{{\mathcal{O}}(1)}}\) for bounded genus graphs follows from [29]. For planar graphs, Weinberg [34] (1966) gave a very simple quadratic-time algorithm for testing isomorphism of planar graphs. This was improved by Hopcroft and Tarjan [19] to \({\mathcal{O}}(n\log{n})\). Building on this earlier work, Hopcroft and Wong [20] published an article in 1974, in which they described a linear-time algorithm for testing isomorphism of planar graphs. An interesting question is whether the result of Hopcroft and Wong [20] can be generalized also for the bounded genus graphs, i.e., whether the isomorphism problem for graphs of bounded genus can be solved in time \(f(g)\cdot n\), for some computable function \(f\). This motivates the study of the isomorphism problem for embedded graphs. Recently, a linear-time algorithm was announced [22] for testing isomorphism of bounded genus graphs. The proposed algorithm employs the results of this article as a subroutine. For graphs on surfaces of higher genus, the graph isomorphism problem seems much harder. This can be explained in the following way. We can rather easily reduce the problem to \(3\)-connected graphs. For planar graphs, the famous result of Whitney [35] says that embeddings of \(3\)-connected planar graphs in the plane are (combinatorially) unique. However, for infinitely many surfaces \(S\) of non-positive Euler characteristics, there exist \(3\)-connected graphs with exponentially many embeddings into \(S\); see, for example, [6] and the references therein. This makes an essential difference between planar graphs and graphs of higher genera.

By a topological map we mean a \(2\)-cell decomposition of a closed compact surface, i.e., an embedding of a connected graph into a surface such that every face is homeomorphic to an open disc. An isomorphism of two maps is an isomorphism of the underlying graphs,which preserves the vertex-edge-face incidences. In particular, a map isomorphism induces a homeomorphism of the underlying surfaces. By the size of a map \(M\), denoted \(\|M\|\), we mean the number of edges of \(M\). A quadratic algorithm of complexity \((\|M_{1}\|+\|M_{2}\|)^{2}\) testing isomorphism between general maps \(M_{1}\) and \(M_{2}\) (regardless of genus) has been known for a long time, see Corollaries 2.8 and 2.9 and the discussion in the end of Section 2.

Our ambition is not just to decide the isomorphism problem between maps in linear time but to determine the set \({{\rm Iso}}(M_{1},M_{2})\) of all isomorphisms between two maps. The latter problem is closely related to the problem of computation of generators of the automorphism group of a map. For the sphere, Colbourn and Booth [10] proposed a way to modify the Hopcroft-Wong algorithm [20] to compute the generators of the automorphism group of a spherical map. However, they state the following: “We… base our automorphism algorithms on the Hopcroft-Wong algorithm. Necessarily, we will only be able to sketch our procedure. A more complete description and a proof of correctness would require a more thorough analysis of the Hopcroft-Wong algorithm than has yet appeared in the literature.” Sadly, the situation has not changed since, and the only available description of the Hopcroft-Wong algorithm is the extended abstract [20], which contains no proof of the correctness and running time.¹ Our contribution also fills in this gap, and we obtain better insight into the Hopcroft-Wong algorithm by solving the problem in a greater generality; see [23] as well. Roughly speaking, the key idea of the Hopcroft-Wong algorithm is to try to apply contractions of edges to obtain two smaller maps, which are isomorphic if and only if the original maps are. In order to do this, in each step of the algorithm, the contracted edges must be chosen canonically in a way that they form an independent set invariant with respect to the action of the automorphism group. Unfortunately, a canonical choice is not always possible. In the sphere, this situation occurs only for a very special family of maps. If this happens, the Hopcroft-Wong algorithm employs another reduction which is not locally defined. The reductions are applied repeatedly until we obtain an irreducible map. A map \(M\) is irreducible if none of the prescribed reductions applies to \(M\). The original maps are isomorphic if and only if the associated irreducible maps are isomorphic.

It turns out that the impossibility of the canonical choice of the set of edges to be contracted is quite common for maps of higher genera. Therefore, we have decided to change the approach by relaxing the notion of irreducible maps on one side and reducing the amount of reductions just to three on the other side. The Hopcroft-Wong algorithm reduces spherical maps to maps having the same degrees of vertices and also the same degrees of faces (e.g., Platonic solids, cycles and dipoles), while the set of reductions described in Section 3 yields in the spherical case the sporadic family of Platonic and Archimedean maps, and five infinite families listen in Section 4.2. Since all the reductions defined in Section 3 are locally defined, they apply for maps on any orientable surface as well. The underlying surface determines only the set of irreducible maps. For genus \(g \gt 1\), the number of irreducible maps of genus \(g\) is by Proposition 4.1 finite. In Section 5, we introduce special algorithms solving the isomorphism problem for the irreducible maps on the sphere and on the torus. In Section 6, we extend the algorithm to maps on non-orientable surfaces. Further information on the algorithm and its complexity can be found in Section 7.

Our main results read as follows.

Determining the set of all isomorphisms between two maps is closely related to finding the generators of the automorphism group \({\rm Aut}(M)\) of a map \(M\). More precisely, the set of all isomorphisms \(M_{1}\to M_{2}\) can be expressed as a composition \(\psi\circ{\rm Aut}(M_{1})\) where \(\psi:M_{1}\to M_{2}\) is any isomorphism. Thus, our first result goes hand-in-hand with the following.

In this section, we describe in detail a set of elementary reductions defined on labeled oriented maps, given by a quadruple \((D,R,L,\ell)\). The output of each elementary reduction is always a quadruple \((D^{\prime},R^{\prime},L^{\prime},\ell^{\prime})\), satisfying \(D^{\prime}\subseteq D\), \(v(M^{\prime})+e(M^{\prime}) \lt v(M)+e(M)\), and \({\rm Aut}^{+}(M^{\prime})={\rm Aut}^{+}(M)\restriction_{D^{\prime}}\). If none of the reductions apply, the map is a uniform oriented map. This defines a function which assigns to a given oriented map \(M\) a unique labeled oriented map \(U\) with \({\rm Aut}^{+}(M)\cong{\rm Aut}^{+}(U)\). Since the darts of \(U\) form a subset of the darts of \(M\), by Corollary 2.8, every generator of \({\rm Aut}^{+}(U)\) can be extended to a generator of \({\rm Aut}^{+}(M)\) in linear time. We deal with the uniform oriented maps in Section 4. Moreover, the size of the automorphism group of a map of genus \(g \gt 1\) is bounded by a function of \(g\) (and hence any generating set), see Corollary 4.2. On the other hand, for \(g=0,1\), it is known that the automorphism group of a map can be generated by at most four generators, and our algorithm identifies a set of generators with at most four elements; see the classifications of spherical and toroidal groups [11, 32].

After every elementary reduction, to ensure that \({\rm Aut}^{+}(M^{\prime})\cong{\rm Aut}^{+}(M)\), we need to define a new labeling \(\ell^{\prime}\). More precisely, the key property of the reductions reads as follows: the set of darts \(D^{\prime}\) of the map \(M^{\prime}\) is an \({\rm Aut}^{+}(M)\)-invariant subset of the set \(D\) of darts of \(M\), and the restriction \({\rm Aut}^{+}(M)_{\restriction{D^{\prime}}}={\rm Aut}^{+}(M^{\prime})\). To this end, in the whole section, we assume that we have an injective function \({{\bf Label}}\colon\mathbb{N}\times\bigcup_{k=1}^{\infty}{\mathcal{T}}^{k}\to{ \mathcal{T}}\), where \({\mathcal{T}}\) is the set of all integer-valued planted trees. Moreover, we assume that the root of \({{\bf Label}}(t,T_{1},\dots,T_{k})\) contains the integer \(t\), corresponding to the current step of the reduction procedure. After every elementary reduction, this integer is increased by one. In Section 7, we show how to evaluate \({{\bf Label}}\) in linear time.

Normalization. Our first aim is to reduce an input map to a face-normal map, since by Theorem 2.5 the degree of a light vertex in a face-normal map is bounded by a function of the genus. The following reductions remove faces of degree one and two. Normalization is of the highest priority and it is applied until the map is one of the following: (i) face-normal, (ii) bouquet, (iii) dipole. In the cases (ii) and (iii), the whole reduction procedure stops with a uniform map. In the case (i), the reduction procedure continues with further reductions. We describe the reduction formally.

For technical reasons, we split the reduction into two parts: deletion of loops, denoted by \({{\bf Loops}}(M)\), and replacement of a dipole by an edge, denoted by \({{\bf Dipoles}}(M)\).

Reduction Loops. If \(M=(D,R,L,\ell)\) with \(v(M) \gt 1\) contains loops, we remove them. Let \({\mathcal{L}}\) be the list of all maximal sequences of darts of the form \(s=\{x_{1},x_{1}^{-1},\dots,x_{k},x_{k}^{-1}\}\), where \(Rx_{i}=x_{i}^{-1}\), for \(i=1,\dots,k\), \(Rx_{i}^{-1}=x_{i+1}\) for \(i=1,\dots,k\), and \(Rx_{k}^{-1}\neq x_{1}\). By definition, \(R^{-1}Lx_{i}=x_{i}\), hence \(x_{i}\) bounds a \(1\)-face, for \(i=1,\dots,k\); see Figure 1. Moreover, for each such sequence \(s\), all the darts \(x_{i}\) are incident to the same vertex \(v\in V(M)\). We say that the unique vertex \(v\) with \(R_{v}=(x_{0},x_{1},x_{1}^{-1},\dots,x_{k},x_{k}^{-1},x_{k+1},\dots)\) is incident to \(s\). We call the darts \(x_{0}\) and \(x_{k+1}\) the bounding darts of the sequence \(s\).

The new map \(M^{\prime}=(D^{\prime},R^{\prime},L^{\prime},\ell^{\prime})=:{{\bf Loops}}(M)\) is defined as follows. First, we put \(D^{\prime}:=D\setminus\bigcup_{s\in{\mathcal{L}}}s\), and \(L^{\prime}:=L_{\restriction{D^{\prime}}}\). Let \(s=\{x_{1},x_{1}^{-1},\dots,x_{k},x_{k}^{-1}\}\in{\mathcal{L}}\) with bounding darts \(x_{0}\) and \(x_{k+1}\). If \(v\) is incident to \(s\), then we put \(R_{v}^{\prime}:=(x_{0},x_{k+1},\dots)\), else we put \(R_{v}^{\prime}:=R_{v}\). Moreover, we put \(\ell^{\prime}(x_{0}):={{\bf Label}}(t,a_{0},\dots,a_{k})\) and \(\ell^{\prime}(x_{k+1}):={{\bf Label}}(t,a_{k+1},b_{k},\dots,b_{1})\), where \(t\) is the current step, \(a_{i}=\ell(x_{i})\), for \(i=0,\dots,k+1\), and \(b_{i}=\ell(x_{i}^{-1})\), for \(i=1,\dots,k\). For every \(x\in D^{\prime}\) which is not a bounding dart in \(M\), we put \(\ell^{\prime}(x):=\ell(x)\). We obtain a well-defined map \(M^{\prime}\) with no faces of valence one; see Figure 1.

Reduction Dipoles. Let \(M=(D,R,L,\ell)\) with \(v(M) \gt 2\) contain dipoles. Let \({\mathcal{L}}\) be the list of all maximal sequences \({\bf s}=x_{1},\dots,x_{k}\) of darts, \(k \gt 1\), satisfying \(Rx_{i}=x_{i+1}\), \((R^{-1}L)^{2}x_{i}=x_{i}\), and either \(Rx_{k}\neq x_{1}\) or \(Rx_{1}^{-1}\neq x_{k}^{-1}\); see Figure 2. Let \({\bf s}^{-1}:=(x_{k}^{-1},\dots,x_{1}^{-1})\in{\mathcal{L}}\) be the inverse sequence. There are vertices \(u\) and \(v\) such that \(R_{u}=(y_{1},{\bf s},y_{2},\dots)\) and \(R_{v}=(z_{1},{\bf s}^{-1},z_{2},\dots)\), for some \(y_{1},y_{2},z_{1},z_{2}\in D\). The symbol \({\bf s}\) in the definition of \(R_{v}\) and \(R_{u}\) means that one has to substitute \({\bf s}\) by the corresponding sequence of darts. At least one of the sets \(\{y_{1},y_{2}\}\), \(\{z_{1},z_{2}\}\) is non-empty since otherwise \(v(M)=2\) and \(M\) is a dipole. We say that \(u,v\) are incident to \({\bf s},{\bf s}^{-1}\), respectively; see Figure 2.

The new map \(M^{\prime}=(D^{\prime},R^{\prime},L^{\prime},\ell^{\prime})=:{{\bf Dipoles}}(M)\) is defined as follows. First, we put

Let \({\bf s}=(x_{1},\dots,x_{k})\in{\mathcal{L}}\). If \(u\) and \(v\) are incident to \(\bf s\) and \({\bf s}^{-1}\), respectively, then we put \(R_{u}^{\prime}:=(y_{1},x_{1},y_{2}\dots)\) and \(R_{v}^{\prime}:=(z_{1},x_{k}^{-1},z_{2},\dots)\), else we put \(R_{u}^{\prime}:=R_{u}\). Next, we put \(L^{\prime}x_{1}:=x_{k}^{-1}\), \(L^{\prime}x_{k}^{-1}:=x_{1}\), and \(L^{\prime}x:=Lx\) if \(x\notin s\) for all \({\bf s}\in{\mathcal{L}}\). Finally, we put \(\ell^{\prime}(x_{1}):={{\bf Label}}(t,a_{1},\dots,a_{k})\) and \(\ell^{\prime}(x_{k}^{-1}):={{\bf Label}}(t,b_{k},\dots,b_{1})\), where \(t\) is the current step, \(a_{i}=\ell(x_{i})\) and \(b_{i}=\ell(x_{i}^{-1})\), for \(i=1,\dots,k\). We put \(\ell^{\prime}(x):=\ell(x)\) for every \(x\notin{\bf s}\in{\mathcal{L}}\), where \({\bf s}\) ranges through all elements of \({\mathcal{L}}\). We obtain a well-defined map \(M^{\prime}\) with no \(2\)-faces; see Figure 2.

Face-Normal Maps. The input is a labeled face-normal oriented map \(M=(D,R,L,\ell)\) and a list \({\mathcal{L}}\) of all light vertices of degree \(d\) which have at least one heavy neighbour. For every vertex \(v\in{\mathcal{L}}\), we denote by \(u_{0},\dots,u_{k-1}\), for some \(1\leq k\leq d\), the cyclic sequence of all heavy neighbours of \(v\), following the prescribed orientation of the underlying surface. Denote by \(x_{0},x_{1},\dots,x_{k-1}\) the darts based at \(u_{0},u_{1},\dots,u_{k-1}\), joining \(u_{j}\) to \(v\) for \(j=0,\dots,k-1\). Let \(R_{u_{i}}=(y_{i},x_{i},z_{i},\dots)\), for \(i=0,\dots,k-1\), and letwhere each \(A_{i}\) is a (possibly empty) sequence of darts.

The new map \(M^{\prime}=(D^{\prime},R^{\prime},L^{\prime},\ell^{\prime})=:{{\bf Delete}}(M)\) is defined as follows. We set \(D^{\prime}:=D\) and \(L^{\prime}:=L\). For a heavy vertex \(w\) with no light neighbour, we have \(R_{w}^{\prime}:=R_{w}\). If \(v\in{\mathcal{L}}\), with the above notation, we set \(R_{u_{i}}^{\prime}:=(y_{i},A_{i},x_{i},x_{i-1}^{-1},z_{i},\dots)\). Moreover, we set \(\ell^{\prime}(x_{i}):={{\bf Label}}(t,\ell(x_{i}))\) and \(\ell^{\prime}(x_{i}^{-1}):={{\bf Label}}(t,\ell(x_{i}^{-1}))\), where \(t\) is the current step number; see Figure 3.

In this section, we provide a linear-time algorithm computing the automorphism group of an irreducible oriented map of a fixed genus and the sets of orientation-preserving isomorphisms between two irreducible maps of a fixed genus. A labeled oriented map \(M\) is irreducible if none of the reductions introduced in Section 4 applies to \(M\). The analysis is splits into three parts: maps with negative Euler characteristics (Section 4.1), maps on the sphere (Section 4.2), and maps on the torus (Section 5). Solving in linear time the problem of determining the automorphism group and deciding the isomorphism problem for irreducible maps on the torus is exceptionally difficult. Therefore, the whole Section 5 is dedicated to toroidal maps.

By definition, the toroidal irreducible maps are uniform face-normal maps. The universal covers of uniform toroidal maps are uniform tilings of the Euclidean plane (infinite maps with finite vertex and face degrees). There are 12 such tilings; see [17, page 63] determined by the local type of vertices. The corresponding local types are \((3,3,3,3,3,3)\), \((4,4,4,4)\), \((6,6,6)\), \(2\times(3,3,3,3,6)\), \((3,3,3,4,4)\), \((3,3,4,3,4)\), \((3,4,6,4)\), \((3,6,3,6)\), \((3,12,12)\), \((4,6,12)\), and \((4,8,8)\). One type occurs in two forms, one is the mirror image of the other. Hence there are \(11\) uniform tilings of the Euclidean plane up to change of global orientation, each is determined by the corresponding local type of its vertices, see Figures 5 and 6. Each of these tilings \(T\) gives rise to an infinite family of toroidal uniform maps as follows. It is well-known that \({\rm Aut}^{+}(T)\) is isomorphic either to the triangle group \(\Delta(4,4,2)\) or to \(\Delta(6,3,2)\). For every uniform tiling \(T\) the group \({\rm Aut}^{+}(T)\) contains an infinite normal subgroup \(H\) of translations generated by two shifts. Every finite uniform toroidal map of the prescribed local type can be constructed as the quotient \(T/K\), where \(K\) is a subgroup of \(H\) of finite index. Recall that the triangle group \(\Delta(k,m,n)\) has a presentationwhere \(k,m,n\) are integers \(\gt 1\). The groups \(\Delta(k,m,n)\) are discrete groups of orientation-preserving automorphisms acting on the sphere, Euclidean plane, or hyperbolic plane, depending on whether \(q=\frac{1}{k}+\frac{1}{m}+\frac{1}{n} \gt 1\), \(q=1\), or \(q \lt 1\). In particular, \(\Delta(k,m,2)\) acts as the group of orientation-preserving automorphisms of \(k\)-valent tiling of a simply connected surface by regular \(m\)-gons. The tiling is Euclidean if and only if \((k,m)\in\{(3,6),(6,3),(4,4)\}\).

From Uniform Face-Normal Toroidal Maps to Homogeneous Maps. We show that each of the uniform maps \(T\) can be reduced to a homogeneous map of type \((4^{4})=(4,4,4,4)\), \((3^{6})=(3,3,3,3,3,3)\), or of type \((6^{3})=(6,6,6)\) such that \({\rm Aut}^{+}(T)\) is preserved.

Homogeneous Maps on Torus. First, we describe how to compute the generators of the automorphism group of unlabeled homogeneous toroidal maps. There are three possible homogeneous types of such maps: \((3^{6})\), \((4^{4})\), and \((6^{3})\). By duality, we may assume that the map is either of type \((4^{4})\), or of type \((3^{6})\). The maps admit a simple description in terms of three integer parameters \(r,s,t\) where \(0\leq t \lt r\). The 4-regular quadrangulation \(Q(r,s,t)\) is obtained from the \((r+1)\times(s+1)\) grid with underlying graph \(P_{r+1}\Box P_{s+1}\) (the Cartesian product of paths on \(r+1\) and \(s+1\) vertices) by identifying the “leftmost” path of length \(s\) with the “rightmost” one (to obtain a cylinder) and identifying the bottom \(r\)-cycle of this cylinder with the top one after rotating the top clockwise for \(t\) edges. In other words, the quadrangulation \(Q(r,s,t)\) is the quotient of the integer grid \(\mathbb{Z}\Box\mathbb{Z}\) determined by the equivalence relation generated by all pairs \((x,y)\sim(x+r,y)\) and \((x,y)\sim(x+t,y+s)\). The 6-regular triangulation \(T(r,s,t)\) is obtained from \(Q(r,s,t)\) by adding all diagonal edges joining \((x,y)\) with \((x+1,y+1)\). And the 3-regular hexangulations \(H(r,s,t)\) of the torus are just duals of triangulations \(T(r,s,t)\). It follows that (in the unlabeled case) one can reduce the isomorphism problem for homogeneous maps to computation of parameters \(r,s,t\) for the quadrangular grids.

The parameters \(r,s,t\) depend on the choice of one of the edges incident with a chosen reference vertex \(v_{0}\). Let us describe the 6-regular case \(T(r,s,t)\) first. Let the clockwise order of the edges around \(v_{0}\) be \(e_{1},e_{2},\dots,e_{6}\). We start with \(e_{1}\) and take the straight-ahead walk (when we arrive to a vertex \(u\) using an edge \(e\), we continue the walk with the opposite edge in the local rotation around \(u\)). When we come back for the first time to a vertex we have already traversed, it can be shown that this vertex must be \(v_{0}\) and that we arrive through the edge \(e_{4}\), which is opposite to the initial edge \(e_{1}\). This way the straight-ahead walk closes up into a straight-ahead cycle \(C=v_{0}v_{1}\dots v_{r-1}v_{0}\). We let \(r\) be the length of this cycle. Now, let us start a straight-ahead walk from \(v_{0}\) with the initial edge \(e_{2}\). Let \(s \gt 0\) be the number of steps on this walk until we reach a vertex, say \(v_{t}\) (\(0\leq t \lt r\)), on the cycle \(C\), for the first time. This determines the three parameters \(r,s,t\) and it can be shown that the map is isomorphic to the map \(T(r,s,t)\) described above. A parametrization by \((r,s,t)\) in the 4-regular case is obtained similarly except that we do not have the directions of the edges \(e_{3}\) and \(e_{6}\). See Figure 7 for an example. In particular, this proves the well-known fact that the abelian group \(T=\langle a,b\rangle\) satisfying relations \(ra=0\) and \(ta=sb\) acts regularly on the vertices of \(T(r,s,t)\). In particular, it is a Cayley graph based on \(T\).

The following two lemmas summarize the above analysis of the map isomorphism (automorphism) problem on homogeneous toroidal maps.

The following fact follows from the above lemma.

It is well-known that the group of translations \(T\leq{\rm Aut}^{+}(M)\) can always be written as a direct product of two cyclic groups. In particular, we have the following.

Labeled Homogeneous Maps on the Torus. For technical reasons, we transform the dart-labels of a homogeneous toroidal map \(M\) to vertex-labels. The transformation depends on the choice of the edges \(e_{1}\) and \(e_{2}\) incident to the vertex \(v_{0}\). The couples \((v_{0},e_{1})\), \((v_{0},e_{2})\) determine sets of oriented horizontal and vertical cycles, respectively. If \(u\) is any vertex, it is contained in exactly one horizontal cycle \(H_{u}\), and exactly one vertical cycle \(C_{u}\). Thus there is a unique dart \(f_{1}\in H_{u}\) and \(f_{2}\in C_{u}\) incident to \(u\). Let \((f_{1},f_{2},f_{4},f_{5})\) be the rotation of darts at \(u\) if the type of \(M\) is \((4^{4})\) and \((f_{1},f_{2},f_{3},f_{4},f_{5},f_{6})\) if it is of type \((3^{6})\). We set \(\ell(u)=(\ell(f_{1}),\ell(f_{2}),\ell(f_{4}),\ell(f_{5}))\) in the first case, and \(\ell(u)=(\ell(f_{1}),\ell(f_{2}),\ell(f_{3}),\ell(f_{4}),\ell(f_{5}),\ell(f_{6 }))\) in the second case. Similarly as in the spherical case, the labels of vertices are encoded by integers.

Clearly, every label-preserving automorphism of \(M\) is an automorphism of the associated unlabeled homogeneous map \(\tilde{M}\). It follows that \(G={\rm Aut}^{+}(M)\leq{\rm Aut}^{+}(\tilde{M})=T\cdot H\), where \(T\) and \(H\) are the subgroups from Lemma 5.4. However, the subgroup \(T_{1}=G\cap T\) may not be transitive on the vertices of \(M\). An analogue of Lemma 5.4 holds for the action of \(G\) on the vertices of \(M\).

Transformation to Orthogonal Grid. Lemma 5.5 can be used to transform the shifted toroidal grid \({\mathcal{G}}\) with parameters \(r,s,t\) to the orthogonal toroidal grid \({\mathcal{G}}^{\perp}\) with parameters \(r^{\prime},s^{\prime}\). Note that the underlying graph may change, but both \({\mathcal{G}}\) and \({\mathcal{G}}^{\perp}\) are Cayley graphs based on the group \(\tilde{T}\), therefore, the vertex-labeling naturally transfers. More precisely, let \(\psi\) be an isomorphism of the actions of \(\tilde{T}\) on the vertex-sets of the original and of the orthogonal grid. Then the labeling of the vertices on the orthogonal grid is given by setting \(\ell(\psi(v))=\ell(v)\), where \(v\) ranges through the vertices of \({\mathcal{G}}\). We have the following.

Isomorphisms between Labeled Orthogonal Grids. Denote by \(\overrightarrow{X}\) a labeled orthogonal grid \(X\) of size \(r\times s\) with a parametrization with respect to origin \(v_{0}=v[0,0]\) and two chosen orthogonal darts \(x_{1}\), \(x_{2}\) based at \(v_{0}\). We can introduce a coordinate system by setting \(v=v[i,j]\), \(i\in\mathbb{Z}_{r}\) and \(j\in\mathbb{Z}_{s}\) if \(v\in V(\overrightarrow{X})\) can be reached from \(v_{0}\) by the oriented horizontal path of length \(i\) followed by the oriented vertical path of length \(j\). By a vertical cycle\(X_{i}\), \(i\in\mathbb{Z}_{r}\) we mean the cyclic vector \((v[i,0],v[i,1],\dots,v[i,s-1])\). Similarly, a horizontal cycle\(Y_{j}\), \(j\in\mathbb{Z}_{s}\) is the cyclic vector \((v[0,j],v[1,j],\dots,v[r-1,j])\). An isomorphism between two labeled orthogonal grids takes an oriented horizontal cycle onto an oriented horizontal cycle, and an oriented vertical cycle onto an oriented vertical cycle. In particular, vertex-stabilizers are trivial. We define the label of \(X_{i}\) by setting \({\mathcal{L}}(X_{i})=(\ell(v[i,0]),\ell(v[i,1]),\dots,\ell(v[i,s-1]))\). Observe that \({\mathcal{L}}(X_{i})\) depends on the parametrization defined by \(v_{0}\), \(x_{1}\) and \(x_{2}\). The set of vertical cycles of \(\overrightarrow{X}\) will be denoted by \({{\rm Cyc}}(\overrightarrow{X})\). There is a natural cyclic order of the set of vertical cycles given by \({\rm succ}(X_{i})=X_{i+1}\). For \(r\geq 2\), two consecutive cycles \(X_{i}\), \(X_{i+1}\), induce a ladder \({{\rm La}}(X_{i})\) with vertex set \(V(X_{i})\cup V(X_{i+1})\) and edges of the form \((v[i,j],v[i,j+1])\), \((v[i+1,j],v[i+1,j+1])\) and \((v[i,j],v[i+1,j])\), for \(j\in\mathbb{Z}_{s}\). For two consecutive labels \({\mathcal{L}}(X_{i})=(a_{0},\dots,a_{s-1})\) and \({\mathcal{L}}(X_{i+1})=(b_{0},\dots,b_{s-1})\) we set \({\mathcal{L}}(X_{i},X_{i+1})=(c_{0},\dots,c_{s-1})\), where \(c_{i}\) are first unused integers by \(\ell\) and \(c_{i}=c_{j}\) if and only if \((a_{i},b_{i})=(a_{j},b_{j})\). The integers \(c_{j}\), \(j\in\mathbb{Z}_{s}\), will be understood to be the labels of the vertices of the cycle \(X^{\prime}_{i}\) arising by contracting the spokes \((v[i,j],v[i+1,j])\) of the ladder \({{\rm La}}(X_{i})\). The ladder \({{\rm La}}(X_{i})\) is uniquely defined by an oriented cycle \({X^{\prime}}_{i}\), with vertex-set \(\{u[i,0],u[i,1],\dots,u[i,s-1]\}\), and labeling \(\ell(u[i,j])=(\ell(u[i,j],\ell(u[i+1,j]))\). Hence, the isomorphism problem for two ladders \({{\rm La}}(X_{i})\) and \({{\rm La}}(X_{m})\) can be decided by applying the algorithm \({\rm IsoCycle}({X^{\prime}}_{i},{X^{\prime}}_{m})\).

A labeled orthogonal grid \(\overrightarrow{X}\) of dimension \(r\times s\) will be called cyclic, if for every \(i\in\mathbb{Z}_{r}\), \({{\rm La}}(X_{i})\cong{{\rm La}}(X_{i+1})\). Denote by \({{\rm La}}(\overrightarrow{X})={{\rm La}}(X_{0})\). For two consecutive ladders \({{\rm La}}(X_{i}),{{\rm La}}(X_{i+1})\) define the \(i\)-th vertical shift \(h_{i}\) as the minimum integer \(h_{i}\in\mathbb{Z}_{s}\) such that there is an isomorphism \({{\rm La}}(X_{i})\to{{\rm La}}(X_{i+1})\) taking \(v[i,0]\mapsto v[i+1,h_{i}]\). One can easily see that in a cyclic grid \(\overrightarrow{X}\), all the vertical shifts \(h_{i}\) are equal. We set \(h(\overrightarrow{X})=h_{0}\in\mathbb{Z}_{s}\) to be the vertical shift of \(\overrightarrow{X}\). In particular, \(\overrightarrow{X}\) admits an automorphism \(\rho\) taking \(v[i,j]\mapsto v[i+1,j+h]\).

The main idea of the following algorithm is to mimic \({\rm IsoCycle}(\overrightarrow{X},\overrightarrow{Y})\) in dimension two, where the vertical cycles \(X_{i}\) and the ladders \({{\rm La}}(X_{i})\), \(i\in\mathbb{Z}_{r}\), will play the role of vertices and edges of a cycle of length \(r\). Moreover, the vertex \(X_{i}\) is labeled by the isomorphism class of \({{\rm La}}(X_{i})\). Applying Steps 1–6, we get associated cyclic grids with the same automorphism group. In Step 7 the two cyclic grids are compared.

For a map \(M\) on a non-orientable surface \(S\), we reduce the problem of computing the generators of \({\rm Aut}(M)\) to the problem of computing the generators of \({\rm Aut}^{+}(\widetilde{M})\), where \(\widetilde{M}\) is the antipodal double cover over \(M\).

Given a map \(M=(F,\lambda,\rho,\tau)\) on a non-orientable surface of genus \(\gamma\), we define the antipodal double cover \(\widetilde{M}=(D,R,L)\) by setting \(D:=F\), \(R:=\rho\tau\), and \(L:=\tau\lambda\). Since \(M\) is non-orientable, we have \(\langle R,L\rangle=\langle\lambda,\rho,\tau\rangle\), so \(\langle R,L\rangle\) is transitive and \(\widetilde{M}\) is well-defined. For more details on this construction see [28]. We note that \(\widetilde{\chi}=2\chi\), where \(\widetilde{\chi}\) and \(\chi\) is the Euler characteristic of the underlying surface of \(\widetilde{M}\) and \(M\), respectively. Note that one can use Theorem 2.3 to check (in linear time) whether \(M=(F;\lambda,\rho,\tau)\) is non-orientable, otherwise the andipodal double cover is not correctly defined, since the group \(\langle R,L\rangle\) is not transitive on the set \(D=F\).

The previous lemma suggests an approach for computing the generators of the automorphism group of \(M\).

To proceed with maps on the projective plane and Klein bottle, we define the action diagram for a permutation group \(G\leq{\rm Sym}(\Omega)\) with a generating set \(S\). To every generator \(g\in S\) we assign a unique color \(c_{g}\). The action diagram \({\mathcal{A}}(G)\) of \(G\) is an edge-colored oriented graph with the vertex set \(\Omega\). There is an oriented edge \(x\to y\) of color \(c_{g}\) if and only \(gx=y\). We first prove the following technical lemma.

The results of this section are summarized by the following.

In this section, we investigate the complexity of various parts of our algorithm. We focus on the routines which complexity was not analyzed above. We argue that it runs in time linear in the size of the input, i.e., in time \({\mathcal{O}}(|D_{1}|+|D_{2}|)\). We show a representation of the function \(\ell\) such that \(\ell(x)\) and \(\ell(y)\) can be compared in constant time. We also describe an implementation of the function \({{\bf Label}}\) that computes the new label in time proportional to the number of its arguments. At the end, we give a summary of the whole algorithm.

Reductions. The data structure to find next reduction is a list of queues, the number of which is bounded by a function of genus. Every time a vicinity of a vertex is modified, it is pushed to the correct queue. At each step we look at the first non-empty queue.

The only difficulty is with updating the local type for every vertex. If there is a large face \(f\) of size \({\mathcal{O}}(v(M))\) incident to a vertex of small degree, we cannot afford to update the local type of every vertex incident to \(f\), since the degree of \(f\) may decrease just by one. To overcome this obstacle we use another trick.

We define the vertex-face incidence map\(\Gamma(M)\) of \(M\) which is a bipartite quadrangular map associated to \(M\). Its vertices are the vertices and centers of faces of \(M\). For every vertex \(v\in V(M)\) and face-center \(f\in F(M)\) of a face incident to \(v\) there is an edge joining \(v\) to \(f\). Note that \(f\) can be multiply incident to \(v\), for each such incidence there is an edge in \(\Gamma(M)\). The map \(\Gamma(M)\) can be alternatively obtained as the dual of the medial map. Every reduction easily translates to a reduction in \(\Gamma(M)\). We update \(\Gamma(M)\) after every elementary reduction. The important property of \(\Gamma(M)\) is that if \(v\) is a vertex of \(M\), then cyclic vector of degrees of the neighbors of \(v\) in \(\Gamma(M)\) is exactly the local type of \(v\) in \(M\). To update the local type of a vertex after a reduction it suffices to look at its cyclic vector of degrees of its neighbors in \(\Gamma\).

Greatest Common Divisor. At several places in the text, we compute the greatest common divisor of more than two numbers. For positive integers \(a,b\), the complexity of computing \(\gcd(a,b)\) can be bounded by \({\mathcal{O}}(\log(\min(a,b)/\gcd(a,b)))\).

If we have a sequence \(a_{0},\dots,a_{n-1}\) of integers in range \([1,N]\), for some \(N\), then the complexity of computing \(\gcd(a_{0},\dots,a_{n-1})\) can be bounded as follows. Put \(g_{0}:=a_{0}\). Then put \(g_{i}:=\gcd(g_{i-1},a_{i})\), for \(i=1,\dots,n-1\). The complexity of computing \(g_{i}\) is \({\mathcal{O}}(\log(\min(g_{i-1},a_{i})/g_{i}))\). In the worst case, this is \({\mathcal{O}}(\log(g_{i-1}/a_{i}))={\mathcal{O}}(\log(g_{i-1})-\log(g_{i}))\). We have

The overall complexity is therefore \({\mathcal{O}}(n+\log(N))\). In our context, \(n\) is the number of darts, i.e. \(n=|D|\), and \(N\) is at most \(n\), so we can compute the \(\gcd\) of \(n\) numbers in linear time.

Labels. In Section 3, we were using the function \(\ell\) as the labeling of a map \(M\) and the injective function \({{\bf Label}}(t,a_{1},\dots,a_{m})\), where \(t\in\mathbb{N}\) denotes the step and every \(a_{i}\) is a label, for constructing new labels.

First, we describe the implementation of labels, i.e., the images of \(\ell\). Every label is implemented as a rooted planted tree with integers assigned to its nodes. A rooted planted tree is a rooted tree embedded in the plane, i.e., by permuting the children of a node we get different trees; see Figure 8. Every planted tree with \(n\) nodes can be uniquely encoded by a 01-string of length \(2n\). Further, we require that the children of every node \(N\) have smaller integers than their nodes. This type of tree is also called a maximum heap. Such a tree can be uniquely encoded by a string (sequence) of integers.

Now we define \({{\bf Label}}\). The integer \(t\) represents the current step of the algorithm. At the start, we have \(t=0\) and the map \(M\) has constant labeling—every dart is labeled by a one-vertex tree with \(0\) assigned to its only vertex. Performing a reduction increments \(s\) by \(1\). For labels (rooted planted trees) \(a_{1},\dots,a_{m}\), the function \({{\bf Label}}(t,a_{1},\dots,a_{m})\) constructs a new rooted planted tree with \(t\) in the root and the root joined to the roots of \(a_{1},\dots,a_{m}\). Clearly this function is injective and can be implemented in the same running time as the corresponding reduction.

Finally, we relabel homogeneous maps by integers. This is necessary mainly for the case when the reductions terminate at cycles since in this case we need to be able to compare labels in constant time. Suppose that we have two homogeneous maps \(M_{1}\) and \(M_{2}\) with the corresponding sets of labels \({\mathcal{T}}=\{T_{1},\dots,T_{k}\}\) and \({\mathcal{T}}^{\prime}=\{T_{1}^{\prime},\dots,T_{k}^{\prime}\}\). We construct bijections \(\sigma\colon{\mathcal{T}}\to\{1,\dots,k\}\) and \(\sigma^{\prime}\colon{\mathcal{T}}^{\prime}\to\{1,\dots,k\}\) such that after replacing \(T_{i}\) by \(\sigma(T_{i})\) and \(T_{i}^{\prime}\) by \(\sigma^{\prime}(T_{i}^{\prime})\), we get isomorphic maps. To construct \(\sigma\) and \(\sigma^{\prime}\), we replace every tree in \({\mathcal{T}}\) and \({\mathcal{T}}^{\prime}\) by a string of integers. Then we find the lexicographic ordering of \({\mathcal{T}}\) and \({\mathcal{T}}^{\prime}\) by constructing two prefix trees (sometimes in literature called trie); see Figure 8. This lexicographic ordering gives the bijections \(\sigma\) and \(\sigma^{\prime}\). Finally, we need to check if the pre-images of every \(i\) under \(\sigma\) and \(\sigma^{\prime}\) are the same planted trees, otherwise the maps are not isomorphic. This can be easily implemented in linear time.