# Homomorphisms between graphs embedded on surfaces

Delia Garijo Department of Applied Mathematics I, University of Seville,
Spain<EMAIL_ADDRESS>Supported by project PID2019-104129GB-I00/ AEI/
10.13039/501100011033. Andrew Goodall Computer Science Institute (IÚUK),
Charles University, Prague<EMAIL_ADDRESS>Supported by GAČR
22-17398S. Lluís Vena Department of Mathematics, Universitat Politècnica de
Catalunya, Barcelona<EMAIL_ADDRESS>Supported by the a Beatriu de Pinós
Fellowship BP2018-0030 of the AGAUR, Horizon’s 2020 program cofund.

###### Abstract

We extend the notion of graph homomorphism to cellularly embedded graphs
(maps) by designing operations on vertices and edges that respect the surface
topology; we thus obtain the first definition of map homomorphism that
preserves both the combinatorial structure (as a graph homomorphism) and the
topological structure of the surface (in particular, orientability and genus).
Notions such as the core of a graph and the homomorphism order on cores are
then extended to maps. We also develop a purely combinatorial framework for
various topological features of a map such as the contractibility of closed
walks, which in particular allows us to characterize map cores. We then show
that the poset of map cores ordered by the existence of a homomorphism is
connected and, in contrast to graph homomorphisms, does not contain any dense
interval (so it is not universal for countable posets). Finally, we give
examples of a pair of cores with an infinite number of cores between them, an
infinite chain of gaps, and arbitrarily large antichains with a common
homomorphic image.

###### Contents

  1. 1 Introduction
  2. 2 Maps
    1. 2.1 Deletion and contraction
  3. 3 Map homomorphisms
    1. 3.1 Vertex gluing
    2. 3.2 Duplicate edges
    3. 3.3 Homomorphisms
  4. 4 Cores
    1. 4.1 Basic properties
    2. 4.2 Separating and contractible cross-circuits
    3. 4.3 Cross-circuits and homomorphisms
    4. 4.4 Characterization of map cores
    5. 4.5 The poset of map cores

##  1 Introduction

Homomorphisms between sets with added structure are mappings that preserve
this structure. For example, homomorphisms between graphs are mappings between
their vertex sets that preserve adjacency. For multigraphs (loops and parallel
edges allowed), a homomorphism is defined as a pair of mappings, one on
vertices and the other on edges, which together preserve vertex-edge
incidences. For a sense of the richness of the theory of graph homomorphisms
the reader is referred to [10].

Key to the structural understanding of graph homomorphisms is the notion of a
core [11], and in particular the poset of cores, known as the homomorphism
order. The enumeration of graph homomorphisms connects their theory to
applications in statistical physics: the partition function of the $q$-state
Potts model on a graph, and more generally partition functions of vertex-
colouring models, are instances of homomorphism functions [6] (given by a
weighted enumeration of graph homomorphisms from the given graph to a fixed
edge-weighted graph). These partition functions are in turn intimately related
to the Tutte polynomial of a graph, whose evaluations include enumerations of
colourings and flows. In fact, any evaluation of the Tutte polynomial of a
graph expressible as a homomorphism function is the partition function of a
Potts model on the graph [7]. For graphs cellularly embedded in a surface
(maps), the analogous notions of colourings (or tensions, rather) and flows
(taking non-identity values in a finite group) are counted by evaluations of
the surface Tutte polynomial [8, 9], and have been expressed as partition
functions of edge-colouring models [15]. This leaves the question of whether
these enumerations can be expressed in terms of map homomorphisms as partition
functions of vertex-colouring models on the map. To even begin to answer this
question we need to formulate a definition of map homomorphism that extends
that of graph homomorphism while respecting the topology of the graph
embedding. We will then be able to adapt the fruitful analysis of graph
homomorphisms via the poset of cores to the case of maps.

As we shall relate shortly, how to define homomorphisms between maps, however,
is not so clear, one difficulty consisting in the preservation of both the
combinatorial structure of the graph and the topological structure of the
embedding. Maps have several representations, some emphasizing their
topological structure (cellular embeddings of graphs, ribbon graphs), some
emphasizing their combinatorial structure (vertex-edge-face flags, rotation
systems, graph-encoded maps, Tutte’s permutation axiomatization). What counts
as a map homomorphism may thus depend on which representation is chosen: what
structure is to be preserved exactly? To start on firm ground, isomorphism of
maps has just one candidate for its definition no matter what representation
is chosen.

We use a version of Tutte’s permutation axiomatization of maps [19, Chapter X]
in which three involutions defined on a set of “crosses” (obtained by
quartering edges of the map) describe how to get from one vertex, edge or face
to an adjacent one whilst respecting the topology of the map (a formal
definition is given in Definition 1 below). An isomorphism between maps in
this representation is a bijection between their cross sets that commutes with
the involutions defining the maps. By dropping the bijective condition, we
obtain the definition of map homomorphism given both by Malnič, Nedela, and
Škoviera [16] (restricted to the case of orientable surfaces) and by Litjens
and Sevenster [15] (restricted to locally bijective mappings, the context
being universal covers of graphs). Map homomorphisms defined in this way
preserve local combinatorial and topological structure (such as vertex-edge-
face incidences and vertex rotations) but, in general, do not preserve global
topological parameters such as orientability or genus.

We formulate a new definition of map homomorphism (Definition 22) that ensures
that homomorphisms preserve the surface topology; our definition is mainly
based on a vertex identification operation that we call _vertex gluing_.
Vertex gluing, defined in terms of cross permutations (Definition 8), has the
following interpretation in the representation of a map as a cellular
embedding of a graph in a surface: two vertices can be identified under this
operation if they can be moved continuously toward each other until they
coincide without crossing any edges, or if they lie in different connected
components; vertex gluing can be realized as the insertion of an edge (joining
the vertices to be identified in a way that preserves genus and orientability)
followed by its contraction. Any other rule of identifying vertices defined
for maps generally is either a special case of vertex gluing or fails to
preserve genus and orientability in some instances. We then define a map
homomorphism as a sequence of such vertex gluings followed by a sequence of
duplicate edge gluings (the analogue of suppressing parallel edges in graphs).
Map homomorphisms in our sense preserve not only orientability and genus but
also other key topological features (such as the contractibility of facial
walks) and the combinatorial structure of the map (when forgetting the
embedding, a homomorphism between maps gives a homomorphism between their
underlying graphs).

Using our definition of map homomorphism, we define a  _core_ of a map
(Definition 25) as a minimal submap that is a homomorphic image of the whole
map, analogously to how the core of a graph is defined. We establish several
properties of map cores shared with graph cores, and characterize map cores in
terms of a certain type of contractible closed walks, which, roughly speaking,
separate off a disc from the remainder of the map’s surface. This
characterization exploits the “locality” of map homomorphisms, in the sense
that any map homomorphism can be decomposed into a sequence of map
homomorphisms that fix all but a plane submap contained within a contractible
curve on the surface in which the map is embedded. After giving applications
of the characterization, we show that, unlike graph homomorphisms, the map
homomorphism order has no dense intervals, and is thus not universal. Finally,
we produce examples of maps with an infinite number of cores between them, an
example of an infinite chain of gaps, and arbitrarily large antichains of
cores sharing a common homomorphic image.

We would also like to highlight that another contribution of our work is a
purely combinatorial formulation for various topological features of a map in
its representation as a cellular embedding of a graph in a closed surface,
such as the contractibility of closed walks. (A more general notion of
contractibility is needed than that given by Mohar and Thomassen [17], which
does not include closed walks that revisit edges within its scope, while
Cabello and Mohar [2] give a topological definition of contractibility not
straightforward to translate into combinatorial terms.)

The paper is organized as follows. In Section 2 we use a permutation
axiomatization for maps to develop the formalism required for later
constructions and proofs. Section 2.1 focuses on the operations of deletion
and contraction of edges in maps. By considering the effect of these
operations on the various map parameters such as connectivity, genus and
orientability, we arrive at eleven types of map edge (compared to the three
edge types of ordinary, bridge and loop for multigraphs). These types serve to
indicate both the combinatorial and topological role an edge plays in the map.

Section 3 is devoted to developing the notion of a homomorphism between maps.
In Section 3.1 we give a formal account of the operation of vertex gluing, and
in Section 3.2 we define the operation of duplicate edge gluing. In Section
3.3 we use vertex and duplicate edge gluings to define what it means to be an
epimorphism from one map onto another, and the already established notion of
isomorphism between maps in order to define what it means to be a monomorphism
from one map into another. By composing an epimorphism and a monomorphism we
finally arrive at what it means to be a homomorphism from one map to another.

Having then in hand the formal definition of a homomorphism between maps,
Section 4 is devoted to the analogue of graph cores for maps. In Sections 4.2
and 4.3 topological notions such as separating and contractible curves are
defined in terms of the permutation representation of maps so as to move
toward the characterization of when a map is a core given in Section 4.4.
Significant differences to graph cores then emerge in the structure of the
partial order on the set of cores under the relation of “being homomorphic to”
(Section 4.5).

##  2 Maps

We use the combinatorial definition of maps based on Tutte’s permutation
axiomatization of cellularly embedded graphs [18], [19, Ch. X] (see also [12,
1]), which is adapted so as to accommodate isolated vertices (maps without
edges). Also, instead of the two involutions and basic permutation of [19,
Axioms X.1 to X.4], we consider three involutions to define the map (as for
generalized maps of dimension $2$ [13, 14, 3], without boundary and with the
artifice of empty permutation cycles to accommodate edgeless maps). We first
introduce some notation.

Permutations of a finite set $C$ are written in function notation, and the
product of permutations is their composition, read from right to left: if
$\alpha,\beta:C\to C$ are two permutations then $\alpha\beta$ is defined for
$c\in C$ by $\alpha\beta(c)=\alpha(\beta(c))$. Parentheses are used to enclose
cyclic permutations and to indicate the element being mapped; in the first
case we add some spacing between the parenthesis and the elements of the
cycle, and we may drop several in the second case (writing $\alpha c$ for
$\alpha(c)$, note that we use Latin characters for the crosses while Greek
characters for the permutations). For a sequence
$\mathbf{x}=(x_{1},x_{2},\dots,x_{k})$ of distinct elements in $C$, the
permutation $(\;\;x_{1}\;\;\;x_{2}\;\;\;\cdots\;\;\;x_{k}\;\;)$ in cycle
notation is denoted by $(\;\mathbf{x}\;)$. For a permutation $\alpha$, we let
$\alpha\mathbf{x}=(\alpha x_{1},\alpha x_{2},\dots,\alpha x_{k})$; then
$(\;\alpha\mathbf{x}\;)=\alpha(\;\mathbf{x}\;)\alpha^{-1}$. The reverse
sequence $(x_{k},\dots,x_{2},x_{1})$ is denoted by $\overline{\mathbf{x}}$,
and as cyclic permutations
$(\;\overline{\mathbf{x}}\;)=(\;\mathbf{x}\;)^{-1}$. Thus,
$\overline{\alpha\mathbf{x}}$, equal to $\alpha\overline{\mathbf{x}}$, stands
for the sequence $(\alpha x_{k},\dots,\alpha x_{2},\alpha x_{1})$, and
$(\;\alpha\overline{\mathbf{x}}\;)=\alpha(\;\mathbf{x}\;)^{-1}\alpha^{-1}$.

######  Definition 1.

Let $V,E$ and $F$ be finite sets, elements of which are called vertices, edges
and faces, respectively. A map $M=(V,E,F)$ is specified by a tuple
$(C,\alpha_{0},\alpha_{1},\alpha_{2})$ in which $C$ is a finite set, whose
elements are called _crosses_ ; and

  * •

$\alpha_{0}$,$\alpha_{1}$,$\alpha_{2}:C\to C$ are involutions with no fixed
points, that is, $\alpha_{i}^{2}c=c$ and $\alpha_{i}c\neq c$ for each
$i\in\\{0,1,2\\}$ and all $c\in C$;

  * •

the permutations $\alpha_{0}$ and $\alpha_{2}$ commute, that is,
$\alpha_{0}\alpha_{2}=\alpha_{2}\alpha_{0}$;

  * •

each _vertex_ $v\in V$ is associated with a pair of cycles
$(\;\mathbf{x}\;)\;(\;\alpha_{2}\overline{\mathbf{x}}\;)$ in the disjoint
cycle decomposition of the permutation $\alpha_{1}\alpha_{2}$, where
$\mathbf{x}$ is a sequence of crosses (we allow $\mathbf{x}$ to be empty,
making a pair of empty cycles, which corresponds to $v$ being an isolated
vertex);

  * •

the disjoint cycle decomposition of the involution $\alpha_{1}$ is
supplemented by pairs of empty cycles (each pair corresponding to edgeless
components of the map);

  * •

each _edge_ $e\in E$ is associated with a pair of transpositions
$(\;c\;\;\alpha_{0}\alpha_{2}c\;)\;\;(\;\alpha_{0}c\;\;\alpha_{2}c\;)$ for
some cross $c\in C$;

  * •

each _face_ $z\in F$ is associated with a pair of cycles
$(\;\mathbf{y}\;)\;(\;\alpha_{0}\overline{\mathbf{y}}\;)$ in the disjoint
cycle decomposition of the permutation $\alpha_{1}\alpha_{0}$, where
$\mathbf{y}$ is a sequence of crosses (we allow $\mathbf{y}$ to be empty,
which corresponds to $z$ being the face of an isolated vertex).

The vertex and face permutations of $M$ are denoted respectively by

$\tau=\alpha_{1}\alpha_{2}\quad{\rm and}\quad\phi=\alpha_{1}\alpha_{0}.$

A tuple $(C,\alpha_{0},\alpha_{1},\alpha_{2})$ may be alternatively specified
by giving $C,\alpha_{0},\alpha_{2}$ and either the vertex permutation $\tau$
or the face permutation $\phi$; this is the approach taken by Tutte [19,
Chapter X]. Figure 1 illustrates the involutions $\alpha_{0},\alpha_{1}$ and
$\alpha_{2}$, the vertex permutation $\tau$ and the face permutation $\phi$;
in this and later figures it is convenient to use the ribbon graph
representation for better visualization.

Figure 1: (a) The permutations $\alpha_{0},\alpha_{1},\alpha_{2}$ defining a
map acting on a cross $c$, (b) vertex permutation $\tau=\alpha_{1}\alpha_{2}$,
(c) face permutation $\phi=\alpha_{1}\alpha_{0}$. The shaded area indicates a
face, while the dots indicate that there might be some additional edges in
that region.

For a map $M=(V,E,F)$ specified by a tuple
$(C,\alpha_{0},\alpha_{1},\alpha_{2})$ we may write
$M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$ when spelling out what $V,E$ and
$F$ are is not relevant to the context. We shall also write
$v\equiv(\;\mathbf{x}\;)\;(\;\alpha_{2}\overline{\mathbf{x}}\;)$,
$e\equiv(\;\;c\;\;\;\alpha_{0}\alpha_{2}c\;\;)\;(\;\;\alpha_{0}c\;\;\;\alpha_{2}c\;\;)$
and $z\equiv(\;\mathbf{y}\;)\;(\;\alpha_{0}\overline{\mathbf{y}}\;)$ to
indicate the cycles associated to a vertex $v$, an edge $e$, and a face $z$.

Let $v\equiv(\;\mathbf{x}\;)\;(\;\alpha_{2}\overline{\mathbf{x}}\;)$ be a
vertex such that a cross $c$ or $\alpha_{0}c$ appears in $\mathbf{x}$. We say
that $v$ is incident with the edge
$e\equiv(\;\;c\;\;\;\alpha_{0}\alpha_{2}c\;\;)\;(\;\;\alpha_{0}c\;\;\;\alpha_{2}c\;\;)$
and, similarly, edge $e$ is _incident_ with a face $z$ if one cross of $e$
appears in the corresponding pair of cycles of $\phi$ associated with $z$.
With this definition of incidence, $\Gamma=(V,E)$ is the underlying graph of
the map $M=(V,E,F)$ specified by $(C,\alpha_{0},\alpha_{1},\alpha_{2})$.
Isolated vertices of $\Gamma$ are associated with pairs of empty cycles
appended to the cycle decomposition of $\tau$, and a corresponding pair of
empty cycles is appended to the cycle decomposition of $\phi$ (representing
the face surrounding the isolated vertex of $\Gamma$ in the given embedding).

The degree of a vertex $v$ is the number of crosses in one of its associated
cycles from the cycle decomposition of $\tau$, and the degree of the face $z$
is the number of crosses in one of its cycles in $\phi$.

A loop of $M$ is an edge incident with just one vertex, and a link is an edge
incident with two distinct vertices. We denote the number of vertices, edges
and faces of $M$ by $\mathbf{v}(M),\mathbf{e}(M)$ and $\mathbf{f}(M)$,
respectively. Each orbit of $\langle\alpha_{0},\alpha_{1},\alpha_{2}\rangle$
acting on $C$ is a _connected component_ of $M$. Each pair of empty cycles of
$\tau$, associated with an isolated vertex, gives its own connected component.
The number of connected components is denoted by $\mathbf{k}(M)$. A map is
_connected_ if it has just one connected component (the edgeless map on one
vertex is connected).

In a connected map $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$, the number
$\mathbf{o}(M)$ of orbits of
$\langle\alpha_{0}\alpha_{2},\alpha_{1}\alpha_{2}\rangle$ acting on $C$ is
either $1$ or $2$ [19, Theorem X.11]; $M$ is _non-orientable_ if
$\mathbf{o}(M)=1$, and _orientable_ if $\mathbf{o}(M)=2$. Generally, a (not
necessarily connected) map $M$ is said to be orientable if all its components
are orientable, and non-orientable otherwise. The parameter $\mathbf{o}(M)$ is
extended from connected maps to all maps by setting
$\mathbf{o}(M)=\min_{i}\mathbf{o}(M_{i})$ when $M$ has connected components
$\\{M_{i}\\}$.

The _Euler characteristic_ of a map $M$ is defined as

$\boldsymbol{\chi}(M)=\mathbf{v}(M)-\mathbf{e}(M)+\mathbf{f}(M),$

which is used to define the _Euler genus_ by

$\mathbf{eg}(M)=2\mathbf{k}(M)-\boldsymbol{\chi}(M),$

the _genus_ by

$\mathbf{g}(M)=\mathbf{eg}(M)/\mathbf{o}(M),$

and the _signed genus_ by

$\mathbf{sg}(M)=[2\mathbf{o}(M)-3]\mathbf{g}(M)=\frac{2\mathbf{o}(M)-3}{\mathbf{o}(M)}\mathbf{eg}(M)=\begin{cases}\frac{1}{2}\mathbf{eg}(M)&\text{
if }\mathbf{o}(M)=2\\\ -\mathbf{eg}(M)&\text{ if }\mathbf{o}(M)=1\end{cases}.$
(1)

The parameters
$\mathbf{e},\mathbf{f},\mathbf{v},\mathbf{k},\boldsymbol{\chi},\mathbf{g}$ and
$\mathbf{eg}$ are additive over connected components: their value on $M$ is
the sum of their values over each connected component. (The parameters of
orientability $\mathbf{o}$ and signed genus $\mathbf{sg}$ are not additive
over connected components in this way.)

Two maps
$M\equiv(C,\allowbreak\alpha_{0},\allowbreak\alpha_{1},\allowbreak\alpha_{2})$
and
$M^{\prime}\equiv(C^{\prime},\alpha_{0}^{\prime},\alpha_{1}^{\prime},\alpha_{2}^{\prime})$
are _isomorphic_ [19, X.4] if they have the same number of isolated vertices
and there exists a bijection $\beta:C\to C^{\prime}$ such that
$\beta\alpha_{i}c=\alpha_{i}^{\prime}\beta c$ for any $c\in C$ and
$i\in\\{0,1,2\\}$. Note that $\beta$ determines naturally a bijection between
the vertices, edges and faces of the two maps and their respective vertex and
face permutation cycles.

The (geometric) _dual_ of a map $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$
is the map $M^{\ast}\equiv(C,\alpha_{2},\alpha_{1},\alpha_{0})$. The effect of
swapping $\alpha_{0}$ and $\alpha_{2}$ to form the dual gives $\phi=\tau^{*}$
and $\tau=\phi^{*}$: the rotational order of edges around a face of $M$
becomes the rotational order of edges around a vertex in $M^{*}$ and, dually,
the rotational order of edges around a vertex of $M$ becomes the rotational
order of edges around a face of $M^{*}$. The graph underlying $M^{\ast}$ is
given by $\Gamma^{\ast}=(F,E)$ and the edge-face incidence relation.

The permutation representation of a map described in this section is better
suited to our combinatorial approach than the following equivalent topological
definition:

> A map is a graph $\Gamma$ embedded on a surface
> $\Sigma=\Sigma_{1}\sqcup\cdots\sqcup\Sigma_{k}$ (each $\Sigma_{i}$ is a
> compact, connected $2$-manifold without boundary): vertices are points and
> edges are closed curves connecting pairs of vertices that do not intersect,
> except possibly at their endpoints (informally, the graph is drawn on the
> surface in such a way that two edges do not cross).

The idea behind Definition 1 is to describe an embedding of a graph in a
surface by explaining how to go from a point next to a given vertex, edge or
face to a point next to the “adjacent” vertex, edge or face. In order to do
this, edges are cut across and lengthwise into four parts or crosses111As
Tutte explains [19, X.10.2], the term “cross” was suggested by their
representation in diagrams as two crossed arrows, one along an edge and the
other across it, these arrows being reversed by two commuting involutions.
Bryant and Singerman [1] call crosses blades. As mentioned before, the maps
given by Definition 1 can be seen as generalized maps [13, 14, 3], in which
context these crosses are called darts. For Tutte, the term “dart” is used for
a directed edge, corresponding to a pair of crosses related by the product of
the two commuting involutions. and the involutions describing adjacency act on
this set of crosses (see Figure 1).

From a connected combinatorial map as given by Definition 1, we can obtain a
surface $\Sigma$ by gluing open discs along the faces (following one of the
permutations of the crosses of the face); this leads to an embedding of the
underlying graph $\Gamma$ of the map in $\Sigma$ with the property that
removing the vertices and edges of $\Gamma$ from $\Sigma$ leaves a set of
connected components each homeomorphic to a disc. That is to say, a 2-cell
embedding of $\Gamma$. Therefore, a correspondence holds between connected
maps and $2$-cell embeddings of connected graphs in a surface. In particular,
each connected component of the graph is $2$-cell embedded in its own
connected surface. The genus and orientability of a connected surface $\Sigma$
coincide with the genus and orientability of a connected map whose underlying
graph has been 2-cell-embedded in $\Sigma$.

###  2.1 Deletion and contraction

Deletion and contraction of an edge $e$ of a map $M$ are formally defined in
[9], and denoted by $M\backslash e$ and $M/e$, respectively.222The effect of
deletion and contraction of an edge on the involution $\alpha_{1}$ is
described in the proof of Lemma 9. In the case of a link, these operations
have the same effect as deletion and contraction in the underlying graph of
$M$. Deleting a loop of $M$ likewise corresponds in the underlying graph to
deleting the loop. However, the result of contracting a loop depends on its
type, and is not the same as deleting it in the underlying graph: a loop is
_twisted_ if a cross $c$ of the edge and $\alpha_{0}c$ belong to the same
permutation cycle of $\tau$, otherwise, the loop is non-twisted (a cross $c$
of the edge and $\alpha_{2}\alpha_{0}c$ belong to the same permutation cycle
of $\tau$). Contraction of a twisted loop has the effect of “flipping over”
one side of it, and contraction of a non-twisted loop does not correspond at
all to contracting the loop in the underlying graph: indeed, contracting a
non-twisted loop splits its incident vertex into two vertices.

Just as deletion and contraction of edges in a graph are dual operations (with
respect to matroid duality, the relevant matroid here being the cycle matroid
of the graph), so deletion and contraction of edges in maps are dual
operations (with respect to geometric duality). Thus [9, Proposition A.5],

$(M/e)^{\ast}=M^{\ast}\backslash e\qquad\text{ and }\qquad(M\backslash
e)^{\ast}=M^{\ast}/e.$ (2)

Similarly to graphs, the order in which deletion and contraction of the edges
is performed is immaterial, which allows us to define deletion and contraction
of a subset of edges. We let $M\backslash A$ denote the result of deleting the
edges in $A$ (in any order), and $M/B$ the result of contracting the edges in
$B$ (in any order). As shown in [9, Lemma A.6], for a map $M$ and disjoint
subsets $A,B$ of edges of $M$ it follows that $(M\setminus A)/B=(M/B)\setminus
A$.

For the purposes of this paper we only need to know the effect of these
operations on the vertex and face permutations, as described in Tables 1 and 2
(actually, the definition of deletion and contraction can be retrieved from
these tables). For the vertex permutation $\tau$, the effect depends on three
types of edges that have already been defined: a link, a non-twisted loop, and
a twisted loop. For the face permutation $\phi$, we need three further edge
types: a dual link, dual twisted loop or dual non-twisted loop of $M$, defined
respectively as a link, twisted loop or non-twisted loop of the dual map
$M^{\ast}$. Combinations of these give nine edge types; see Figure 2 for some
examples.

edge type in $M$ of $e$
$(\,c\;\alpha_{0}\alpha_{2}c\,)\>(\,\alpha_{0}c\;\alpha_{2}c\,)$ |  link |  non-twisted loop |  twisted loop
---|---|---|---
cycle pair(s) in $\tau$ |  $(c\>\>\mathbf{x})(\alpha_{2}c\>\>\alpha_{2}\overline{\mathbf{x}})$
$(\alpha_{0}\alpha_{2}c\>\>\mathbf{y})\>(\alpha_{0}c\>\>\alpha_{2}\overline{\mathbf{y}})$ |  $(c\>\>\mathbf{x}\>\>\alpha_{0}\alpha_{2}c\>\>\mathbf{y})$
$\>\>(\alpha_{2}\overline{\mathbf{x}}\>\>\alpha_{2}c\>\>\alpha_{2}\overline{\mathbf{y}}\>\>\alpha_{0}c)$ |  $(c\>\>\mathbf{x}\>\>\alpha_{0}c\>\>\mathbf{y})$
$\>\>(\alpha_{2}\overline{\mathbf{x}}\>\>\alpha_{2}c\>\>\alpha_{2}\overline{\mathbf{y}}\>\>\alpha_{0}\alpha_{2}c)$
cycle pair(s) in $\tau$
after deleting $e$ |  $(\mathbf{x})\>(\alpha_{2}\overline{\mathbf{x}})$
$(\mathbf{y})\>(\alpha_{2}\overline{\mathbf{y}})$ |  $(\mathbf{x}\>\>\mathbf{y})\>(\alpha_{2}\overline{\mathbf{x}}\>\>\alpha_{2}\overline{\mathbf{y}})$ |  $(\mathbf{x}\>\>\mathbf{y})\>(\alpha_{2}\overline{\mathbf{x}}\>\>\alpha_{2}\overline{\mathbf{y}})$
$\mathbf{v}(M\backslash e)=$ |  $\mathbf{v}(M)$ |  $\mathbf{v}(M)$ |  $\mathbf{v}(M)$
cycle pair(s) in $\tau$
after contracting $e$ |  $(\mathbf{x}\>\>\mathbf{y})\>(\alpha_{2}\overline{\mathbf{x}}\>\>\alpha_{2}\overline{\mathbf{y}})$ |  $(\mathbf{x})\>(\alpha_{2}\overline{\mathbf{x}})$
$(\mathbf{y})\>(\alpha_{2}\overline{\mathbf{y}})$ |  $(\mathbf{x}\>\>\alpha_{2}\overline{\mathbf{y}})\>(\alpha_{2}\overline{\mathbf{x}}\>\>\mathbf{y})$
$\mathbf{v}(M/e)=$ |  $\mathbf{v}(M)-1$ |  $\mathbf{v}(M)+1$ |  $\mathbf{v}(M)$
Table 1: The effect of deletion and contraction of an edge on the vertex
permutation $\tau$, in which $\mathbf{x}$ and $\mathbf{y}$ are (possibly
empty) sequences of crosses.  edge type in $M$ of $e$
$(\,c\;\alpha_{0}\alpha_{2}c\,)\>(\,\alpha_{0}c\;\alpha_{2}c\,)$ |  dual link |  dual non-twisted loop |  dual twisted loop
---|---|---|---
cycle pair(s) in $\phi$ |  $(c\>\>\mathbf{x})(\alpha_{0}c\>\>\alpha_{0}\overline{\mathbf{x}})$
$(\alpha_{0}\alpha_{2}c\>\>\mathbf{y})\>(\alpha_{2}c\>\>\alpha_{0}\overline{\mathbf{y}})$ |  $(c\>\>\mathbf{x}\>\>\alpha_{0}\alpha_{2}c\>\>\mathbf{y})$
$\>\>(\alpha_{0}\overline{\mathbf{x}}\>\>\alpha_{0}c\>\>\alpha_{0}\overline{\mathbf{y}}\>\>\alpha_{2}c)$ |  $(c\>\>\mathbf{x}\>\>\alpha_{2}c\>\>\mathbf{y})$
$\>\>(\alpha_{0}\overline{\mathbf{x}}\>\>\alpha_{0}c\>\>\alpha_{0}\overline{\mathbf{y}}\>\>\alpha_{0}\alpha_{2}c)$
cycle pair(s) in $\phi$
after contracting $e$ |  $(\mathbf{x})\>(\alpha_{0}\overline{\mathbf{x}})$
$(\mathbf{y})\>(\alpha_{0}\overline{\mathbf{y}})$ |  $(\mathbf{x}\>\>\mathbf{y})\>(\alpha_{0}\overline{\mathbf{x}}\>\>\alpha_{0}\overline{\mathbf{y}})$ |  $(\mathbf{x}\>\>\mathbf{y})\>(\alpha_{0}\overline{\mathbf{x}}\>\>\alpha_{0}\overline{\mathbf{y}})$
$\mathbf{f}(M/e)=$ |  $\mathbf{f}(M)$ |  $\mathbf{f}(M)$ |  $\mathbf{f}(M)$
cycle pair(s) in $\phi$
after deleting $e$ |  $(\mathbf{x}\>\>\mathbf{y})\>(\alpha_{0}\overline{\mathbf{x}}\>\>\alpha_{0}\overline{\mathbf{y}})$ |  $(\mathbf{x})\>(\alpha_{0}\overline{\mathbf{x}})$
$(\mathbf{y})\>(\alpha_{0}\overline{\mathbf{y}})$ |  $(\mathbf{x}\>\>\alpha_{0}\overline{\mathbf{y}})\>(\alpha_{0}\overline{\mathbf{x}}\>\>\mathbf{y})$
$\mathbf{f}(M\backslash e)=$ |  $\mathbf{f}(M)-1$ |  $\mathbf{f}(M)+1$ |  $\mathbf{f}(M)$
Table 2: The effect of contraction and deletion of an edge on the face
permutation $\phi$, in which $\mathbf{x}$ and $\mathbf{y}$ are (possibly
empty) sequences of crosses.

While these nine edge types are sufficient to determine the effect of deletion
and contraction on the map parameters $\mathbf{v}(M)$, $\mathbf{e}(M)$ and
$\mathbf{f}(M)$, in order to determine the effect on the parameters
$\mathbf{k}(M)$ and $\mathbf{o}(M)$, and hence, via Euler’s relation, on
$\mathbf{g}(M)$, two further edge types are needed: a bridge and a dual
bridge. The defining property of a bridge $e$ is that

$\mathbf{k}(M\backslash e)=\begin{cases}\mathbf{k}(M)+1&\mbox{if $e$ is a
bridge,}\\\ \mathbf{k}(M)&\mbox{otherwise.}\end{cases}$ (3)

A dual bridge $e$ is defined with the same property just replacing
$\mathbf{k}(M\backslash e)$ by $\mathbf{k}(M/e)$.

A bridge is a special type of link and dual non-twisted loop (it is a link as
deleting a loop on a vertex $v$ does not affect the connection of $v$ to other
vertices, and it is a dual non-twisted loop as the deletion of an edge $e$ in
disconnecting $M$ increases the number of faces). Similarly, a dual bridge is
a special type of non-twisted loop and dual link. A (dual) link that is not a
bridge is called a (dual) ordinary link.

Figure 2 shows maps that between them contain examples of all eleven edge
types.

Figure 2: Examples of maps that between them contain all eleven edge types;
solid edges (in blue) are of the given type. Transpose entries in the table
are dual maps (those on the diagonal self-dual).

#### Euler characteristic and Euler genus.

The effect of deletion and contraction of an edge $e$ of $M$ on the Euler
characteristic $\boldsymbol{\chi}(M)$ is recorded in Table 3 using the
information given in Tables 1 and 2. As can be seen from the table – and as
shown by Tutte [19, Theorem X.26] – contracting a link does not change the
Euler characteristic (dually, deleting a dual link does not change it either).

edge type in $M$ of $e$ | dual link | dual non-twisted loop | dual twisted loop
---|---|---|---
$\backslash e$ | $/e$ |  $\backslash e$ | $/e$ |  $\backslash e$ | $/e$
link |  0 | 0 |  +2 | 0 |  +1 | 0
non-twisted loop |  0 | +2 |  +2 | +2 |  +1 | +2
twisted loop |  0 | +1 |  +2 | +1 |  +1 | +1
Table 3: Effect of deletion and contraction on the Euler characteristic: the difference $\boldsymbol{\chi}(M\backslash e)-\boldsymbol{\chi}(M)$ (in the column headed $\backslash e$) and $\boldsymbol{\chi}(M/e)-\boldsymbol{\chi}(M)$ (in the column headed $/e$) according to the nine possible edge types for $e$ (without distinguishing bridges). |  dual link |  |
---|---|---|---
| dual ord. link | dual ord. link | dual bridge |  dual non-tw loop |  dual twisted loop
edge type in $M$ of $e$ | $\backslash e$ |  $/e$ |  $\backslash e$ | $/e$ |  $\backslash e$ | $/e$
link ordinary | 0 | 0 |  |  -2 | 0 |  -1 | 0
link bridge |  |  0 |
non-twisted loop | 0 | -2 | 0 |  -2 | -2 |  -1 | -2
twisted loop | 0 | -1 |  |  -2 | -1 |  -1 | -1
Table 4: Effect of deletion and contraction on the Euler genus: the difference
$\mathbf{eg}(M\backslash e)-\mathbf{eg}(M)$ (in the column headed $\backslash
e$) and $\mathbf{eg}(M/e)-\mathbf{eg}(M)$ (in the column headed $/e$)
according to the eleven possible edge types for $e$ (non-twisted loops that
are dual links are divided into those where the dual link is ordinary or a
dual bridge, analogously for links that are dual non-twisted loops.)

Table 3 together with the distinction of bridges and dual bridges yield Table
4, which shows the effect of deletion and contraction on the Euler genus
$\mathbf{eg}(M)$ according to the eleven edge types. The Euler genus is
unchanged when deleting a dual link or a bridge; otherwise it decreases.

#### Orientability.

Tutte showed [19, Theorems X.26 and X.28] that the contraction of a link does
not change orientability (dually, deleting a dual link does not change
orientability either); we include this result as statement (ii) in the
following lemma (its proof is omitted).

######  Lemma 2.

Let $e$ be an edge of a connected map $M$.

  1. (i)

If $\mathbf{o}(M)=2$ then $\mathbf{o}(M\backslash
e)=\mathbf{o}(M)=\mathbf{o}(M/e)$.

  2. (ii)

If $e$ is a dual link then $\mathbf{o}(M\backslash e)=\mathbf{o}(M)$; if $e$
is a link then $\mathbf{o}(M/e)=\mathbf{o}(M)$.

  3. (iii)

If $e$ is a bridge or a dual bridge then $\mathbf{o}(M\backslash
e)=\mathbf{o}(M)=\mathbf{o}(M/e)$.

###### Proof.

Let $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$, and
$e\equiv(\;\;c\;\;\;\alpha_{0}\alpha_{2}c\;\;)\;(\;\;\alpha_{0}c\;\;\;\alpha_{2}c\;\;)$.
If $\mathbf{o}(M)=2$ then $\mathbf{o}(M\backslash e)=2$, as deletion simply
removes the crosses of $e$ from the cycles of the vertex permutation $\tau$ of
$M$, and so it cannot merge the two orientation classes (orbits under the
action of $\langle\tau,\alpha_{0}\alpha_{2}\rangle$). By the same argument
applied to the face permutation $\phi$ (or by duality,
$\mathbf{o}(M^{*})=\mathbf{o}(M)$) we have $\mathbf{o}(M/e)=2$. This proves
statement (i).

When $\mathbf{o}(M)=2$ statement (iii) follows from statement (i). Suppose now
that edge $e$ is a bridge and $\mathbf{o}(M)=1$. The group
$\langle\tau,\alpha_{0}\alpha_{2}\rangle$ acting on $C$ has one orbit: the
graph $\mathcal{G}_{\tau}$ on cycles of $\tau$, in which two cycles are joined
by an edge if there is a cross $a$ in one such that $\alpha_{0}\alpha_{2}a$
lies in the other, is connected (as the number of connected components of
$\mathcal{G}_{\tau}$ corresponds to the number of orbits of
$\langle\tau,\alpha_{0}\alpha_{2}\rangle$ acting on $C$). The cycles

$(\;\;c\;\;\;\mathbf{x}\;\;)\;(\;\;\alpha_{2}c\;\;\;\alpha_{2}\overline{\mathbf{x}}\;\;)\qquad\text{
and
}\qquad(\;\;\alpha_{0}\alpha_{2}c\;\;\;\mathbf{y}\;\;)\;(\;\;\alpha_{0}c\;\;\;\alpha_{2}\overline{\mathbf{y}}\;\;)$

of $\tau$ containing crosses of $e$ have an edge in $\mathcal{G}_{\tau}$
connecting $(\;\;c\;\;\;\mathbf{x}\;\;)$ and
$(\;\;\alpha_{0}\alpha_{2}c\;\;\;\mathbf{y}\;\;)$, and an edge connecting
$(\;\;\alpha_{2}c\;\;\;\alpha_{2}\overline{\mathbf{x}}\;\;)$ and
$(\;\;\alpha_{0}c\;\;\;\alpha_{2}\overline{\mathbf{y}}\;\;)$. After deleting
$e$, these cycles of $\tau$ become the cycles
$(\;\;\mathbf{x}\;\;)(\;\;\alpha_{2}\overline{\mathbf{x}}\;\;)$ and
$(\;\;\mathbf{y}\;\;)\;(\;\;\alpha_{2}\overline{\mathbf{y}}\;\;)$ of the
vertex permutation $\tau^{\prime}$ of
$C\backslash\\{c,\alpha_{0}\alpha_{2}c,\alpha_{0}c,\alpha_{2}c\\}$, and the
other cycles of $\tau$ remain the same. The edge previously joining
$(\;\;c\;\;\;\mathbf{x}\;\;)$ to
$(\;\;\alpha_{0}\alpha_{2}c\;\;\;\mathbf{y}\;\;)$ and that joining
$(\;\;\alpha_{2}c\;\;\;\alpha_{2}\overline{\mathbf{x}}\;\;)$ to
$(\;\;\alpha_{0}c\;\;\;\alpha_{2}\overline{\mathbf{y}}\;\;)$ both disappear in
the new graph $\mathcal{G}_{\tau^{\prime}}$. (Since $e$ is a bridge, the
crosses in $\mathbf{x}$ are not in the same orbit as crosses of $\mathbf{y}$
under the action of $\langle\alpha_{0},\alpha_{1},\alpha_{2}\rangle$ when
restricted to
$C\backslash\\{c,\alpha_{0}\alpha_{2}c,\alpha_{0}c,\alpha_{2}c\\}$.) However,
all other edges in $\mathcal{G}_{\tau}$ remain. Therefore, the graph
$\mathcal{G}_{\tau^{\prime}}$ cannot have four connected components, that is,
the group $\langle\tau^{\prime},\alpha_{0}\alpha_{2}\rangle$ acting on
$C\backslash\\{c,\alpha_{0}\alpha_{2}c,\alpha_{0}c,\alpha_{2}c\\}$ cannot have
four orbits (there is either a single orbit of the action of
$\langle\tau^{\prime},\alpha_{0}\alpha_{2}\rangle$ that contains the crosses
of $\mathbf{x}$ or a single orbit that contains the crosses of $\mathbf{y}$).
This implies that both connected components of $M\backslash e$ cannot be
orientable, and so $\mathbf{o}(M\backslash e)=\mathbf{o}(M)=1$.

Finally, we prove that $M/e$ is non-orientable as the single orbit of
$\langle\tau,\alpha_{0}\alpha_{2}\rangle$ acting on $C$ remains a single orbit
in $M/e$. After the contraction of $e$, the cycles of $\tau$ containing
crosses of $e$ become
$(\;\;\mathbf{x}\;\;\;\mathbf{y}\;\;)\;(\;\;\alpha_{2}\overline{\mathbf{x}}\;\;\;\alpha_{2}\overline{\mathbf{y}}\;\;)$.
Then, the orbit containing the crosses of $\mathbf{x}$ coincides with that
containing crosses of $\mathbf{y}$ under the action of
$\langle\tau,\alpha_{0}\alpha_{2}\rangle$ on
$C\backslash\\{c,\alpha_{0}\alpha_{2}c,\alpha_{0}c,\alpha_{2}c\\}$. Hence,
$\mathbf{o}(M\backslash e)=1$.

The case of a dual bridge in statement (iii) then follows by
$\mathbf{o}(M^{*})=\mathbf{o}(M)$, $(M\backslash e)^{*}=M/e$, and
$(M/e)^{*}=M\backslash e$. ∎

#### Genus and signed genus.

In the following two lemmas we highlight those properties of the (signed)
genus with respect to deletion and contraction of an edge that we shall have
need for later.

######  Lemma 3.

Let $e$ be an edge of a map $M$. Then,

  1. (i)

$\mathbf{sg}(M\backslash e)=\mathbf{sg}(M)$ if and only if $e$ is a dual link
or a bridge.

  2. (ii)

$\mathbf{sg}(M/e)=\mathbf{sg}(M)$ if and only if $e$ is a link or a dual
bridge.

  3. (iii)

$\mathbf{sg}(M\backslash e)=\mathbf{sg}(M)=\mathbf{sg}(M/e)$ if and only if
$e$ is a link and dual link, a bridge, or a dual bridge.

###### Proof.

It suffices to prove statement (i), as (ii) follows by duality and (iii) is
the conjunction of (i) and (ii). Suppose first that $e$ is a dual link or a
bridge. From Table 4 it follows that $\mathbf{eg}(M\backslash
e)=\mathbf{eg}(M)$, and by Lemma 2 we have $\mathbf{o}(M\backslash
e)=\mathbf{o}(M)$. This implies $\mathbf{sg}(M\backslash e)=\mathbf{sg}(M)$ by
Equation (1).

Assume now that $\mathbf{sg}(M\backslash e)=\mathbf{sg}(M)$ and that $e$ is
not a dual link. Then, edge $e$ is a dual loop. If $\mathbf{o}(M)=2$, by Lemma
2, maps $M$ and $M\backslash e$ have the same orientability. Hence
$\mathbf{eg}(M\backslash e)=\mathbf{eg}(M)$, and by Table 4, this equality
holds if and only if $e$ is a bridge.

Suppose now that $\mathbf{o}(M)=1$ and $\mathbf{o}(M\backslash e)=2$
(otherwise we could argue as above). Equation (1) gives
$\mathbf{sg}(M)=-\mathbf{eg}(M)$ and $\mathbf{sg}(M\backslash
e)=\frac{1}{2}\mathbf{eg}(M\backslash e)$. Further, by Table 4 it follows that
$\mathbf{eg}(M\backslash e)\in\\{\mathbf{eg}(M)-1,\mathbf{eg}(M)-2\\}$, which
gives a contradiction as the Euler genus is an integer number. Therefore, $M$
and $M\backslash e$ must have the same orientability, and we can conclude that
$e$ is a bridge with the same argument as for the case $\mathbf{o}(M)=2$. ∎

By Lemma 3 and Table 4, we have $\mathbf{sg}(M\backslash e)=\mathbf{sg}(M)$ if
and only if $\mathbf{eg}(M\backslash e)=\mathbf{eg}(M)$. The effect of edge
deletion on the signed genus, $\mathbf{sg}(M)$, is otherwise to decrease its
absolute value, $\mathbf{g}(M)$:

######  Lemma 4.

Let $e$ be an edge of a map $M$.

  1. (i)

If $M$ is orientable then $\mathbf{g}(M\backslash e)<\mathbf{g}(M)$ unless $e$
is a dual link or a bridge, in which case $\mathbf{g}(M\backslash
e)=\mathbf{g}(M)$.

  2. (ii)

If $M$ and $M\backslash e$ are non-orientable then $\mathbf{g}(M\backslash
e)<\mathbf{g}(M)$ unless $e$ is a dual link or a bridge, in which case
$\mathbf{g}(M\backslash e)=\mathbf{g}(M)$.

  3. (iii)

If $M$ is non-orientable and $M\backslash e$ is orientable then
$2\mathbf{g}(M\backslash e)<\mathbf{g}(M)$.

###### Proof.

If $M$ is orientable, by Lemma 2(i), $M\backslash e$ is orientable. Statement
(i) then follows by Table 4 and the fact that, under the orientability
assumptions, $\mathbf{eg}(M)=2\mathbf{g}(M)$ and $\mathbf{eg}(M\backslash
e)=2\mathbf{g}(M\backslash e)$. Similarly, statement (ii) follows by Table 4
and the fact that $\mathbf{eg}(M)=\mathbf{g}(M)$ and $\mathbf{eg}(M\backslash
e)=\mathbf{g}(M\backslash e)$ (under the orientability assumptions). In both
statements, by Lemma 3, we have $\mathbf{g}(M\backslash e)=\mathbf{g}(M)$ when
$e$ is a dual link or a bridge.

By Lemma 2(i) we cannot have $\mathbf{o}(M)=2$ and $\mathbf{o}(M\backslash
e)=1$, so the remaining case to consider is $\mathbf{o}(M)=1$ and
$\mathbf{o}(M\backslash e)=2$, which is the hypothesis of statement (iii). By
Lemma 2(ii), in this case the edge $e$ must be a dual loop. Referring to Table
4, this implies $\mathbf{eg}(M\backslash e)<\mathbf{eg}(M)$ unless $e$ is a
bridge, in which case by Lemma 2(iii) we have $\mathbf{o}(M\backslash
e)=\mathbf{o}(M)$, contrary to the assumption. Under the given orientability
assumptions, $\mathbf{eg}(M)=\mathbf{g}(M)$ and $\mathbf{eg}(M\backslash
e)=2\mathbf{g}(M\backslash e)$. ∎

#### Euler genus and signed genus of submaps.

Let $v$ be a vertex of a map $M=(V,E,F)$. The map $M-v$ obtained by deleting
$v$ is the map that results by first deleting all edges incident with $v$, and
then removing the empty pair of cycles associated with the now isolated vertex
$v$. A map $N$ is an induced submap of $M$ if $N=M-U$ for some $U\subseteq V$;
similarly, $N$ is a _spanning submap_ of $M$ if $N=M\backslash A$ for some
$A\subseteq E$. An induced submap of a spanning submap of $M$ is called a
_submap_ of $M$. All types of submaps are said to be proper when they are
distinct from the map.

If $M^{\prime}$ is a submap of $M$ then
$\mathbf{v}(M^{\prime})\leq\mathbf{v}(M)$ and
$\mathbf{e}(M^{\prime})\leq\mathbf{e}(M)$, and both the number of components
and the number of faces may change in both directions.333For example, two
loops embedded in the torus are incident with one common face, while deleting
one of the loops leaves the other loop incident with two faces; deleting this
single loop gives an isolated vertex and just one face again. However, we next
show that the Euler genus is monotonous.

######  Lemma 5.

Let $M^{\prime}$ be a submap of a map $M$. Then,

  1. (i)

$\mathbf{eg}(M^{\prime})\leq\mathbf{eg}(M)$, and

  2. (ii)

$\mathbf{eg}(M^{\prime})=\mathbf{eg}(M)$ if and only if
$\mathbf{sg}(M^{\prime})=\mathbf{sg}(M)$.

###### Proof.

Part (i) follows from Table 4: deleting edges does not increase the Euler
genus, and neither does deleting isolated vertices. Part (ii) follows from
Table 4 and Lemma 3. ∎

##  3 Map homomorphisms

The image of a graph homomorphism can be realized as a sequence of
identifications of pairs of distinct vertices, followed by the suppression of
parallel edges (i.e., edges incident with the same pair of vertices, or same
vertex in the case of parallel loops). In order to define the image of a
homomorphism from a map, so that restricted to the underlying graph gives a
graph homomorphism, we need to define how to identify a pair of vertices on a
map so as to produce another map unambiguously, and to define what it means
for edges of a map to be parallel. When identifying vertices in maps we also
need to take into account their incident faces along with the vertex and face
rotations: this is where the permutation axiomatization of maps becomes
essential in order to formulate a well-defined operation on maps analogous to
vertex identification in graphs.

###  3.1 Vertex gluing

In this section we define the operation of vertex gluing in terms of cross
permutations and draw on properties of edge deletion and contraction in order
to establish that vertex gluing is the only general way to identify vertices
in a map while preserving genus and orientability (this property is needed, in
particular, to enable restriction and composition of homomorphisms to be
generally defined). First, we introduce an operation on maps represented by
cross involutions, and go on to explain how vertex gluing can be formalized
using this operation.

######  Definition 6.

Let $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$ be a map and $a,b\in C$. The
map obtained by riffling $a$ and $b$ is
$M^{(\,a\>b\,)}\equiv(C,\alpha_{0},\widetilde{\alpha}_{1},\alpha_{2})$ in
which
$\widetilde{\alpha}_{1}a=\alpha_{1}b,\;\widetilde{\alpha}_{1}b=\alpha_{1}a,$
and $\widetilde{\alpha}_{1}=\alpha_{1}$ on
$C\setminus\\{a,b,\alpha_{1}a,\alpha_{1}b\\}$.

Figure 3 illustrates examples of the riffling operation. With
$\widetilde{\alpha}_{1}a=\alpha_{1}b$ and
$\widetilde{\alpha}_{1}b=\alpha_{1}a$, we have
$\widetilde{\alpha}_{1}(\alpha_{1}a)=\widetilde{\alpha}_{1}^{2}b=b$, and
similarly $\widetilde{\alpha}_{1}(\alpha_{1}b)=a$. The involution
$\widetilde{\alpha}_{1}$ on $C$ obtained by riffling $a$ and $b$ is the result
of conjugating the involution $\alpha_{1}$ by the transposition
$(\;\;a\;\;\;b\;\;)$, or by the transposition
$(\;\;\alpha_{1}a\;\;\;\alpha_{1}b\;\;)$; we thus have
$M^{(\,a\>b\,)}=M^{(\,\alpha_{1}a\>\>\alpha_{1}b\,)}.$ The pair of
transpositions $(\;\;a\;\;\;\alpha_{1}a\;\;)\>(\;\;b\;\;\;\alpha_{1}b\;\;)$ in
the disjoint cycle decomposition of $\alpha_{1}$ is replaced by the pair
$(\;\;a\;\;\;\alpha_{1}b\;\;)\>(\;\;b\;\;\;\alpha_{1}a\;\;)$.

While any pair of distinct crosses $a,b$ of $M$ can be riffled to produce
another map, only under certain conditions are genus and orientability
preserved. We next introduce some terminology to help describe what these
conditions are. A cross $c$ is incident with a vertex $v$ (or a face $z$) if
the pair of permutation cycles associated with $v$ (respectively $z$) contains
$c$. A pair of crosses are coincident with vertex $v$ (face $z$) if they
belong to the same orbit of $\tau$ (respectively $\phi$), i.e. they belong to
the same permutation cycle in the pair of cycles associated with $v$
(respectively $z$). If $a,b$ are coincident with a common face $z$, the
crosses $\alpha_{1}a$ and $\alpha_{1}b$ appear in the conjugate inverse cycle
to $(\;\;a\;\;\;\dots\;\;\;b\;\;\;\dots\;\;)$; thus $a,b$ are coincident with
a common face $z$ if and only if $\alpha_{1}a,\alpha_{1}b$ are coincident with
a common face $z$.

######  Lemma 7.

The operation of riffling crosses $a$ and $b$ preserves genus and
orientability when one of the following conditions holds:

  1. (1)

(i) crosses $a$ and $b$ in $M$ are incident with distinct vertices and
coincident with a common face, or (ii) these crosses are incident with
vertices and faces in different connected components;

  2. (2)

(i) crosses $a$ and $b$ in $M$ are coincident with a common vertex and
incident with distinct faces, or (ii) these crosses are coincident with a
common vertex and face and $\mathbf{k}(M^{(\,a\>b\,)})>\mathbf{k}(M)$.

In other words, in these cases, $\mathbf{sg}(M^{(\,a\>b\,)})=\mathbf{sg}(M).$

###### Proof.

First assume that crosses $a,b$ satisfy condition (1). We define
$M^{+}\equiv(C^{+},\alpha_{0}^{+},\alpha_{1}^{+},\alpha_{2}^{+})$ as the map
obtained from $M$ by adding an edge
$e\equiv(\;\;c\;\;\;\alpha_{0}^{+}\alpha_{2}^{+}c\;\;)\;(\;\;\alpha_{0}^{+}c\;\;\;\alpha_{2}^{+}c\;\;)$
so that $M^{+}\backslash e=M$ and $M^{+}/e=M^{(\,a\>b\,)}$. Explicitly, one
can check that $M^{+}/e=M^{(\,a\>b\,)}$ setting

  * •

$C^{+}=C\sqcup\\{c,\alpha_{0}^{+}c,\alpha_{2}^{+}c,\alpha_{0}^{+}\alpha_{2}^{+}c\\};$

  * •

$\alpha_{0}^{+}=\alpha_{0}$ on $C$;

  * •

$\alpha_{1}^{+}=\alpha_{1}$ on $C\setminus\\{a,b,\alpha_{1}a,\alpha_{1}b\\}$,
and $\alpha_{1}^{+}a=c$, $\alpha_{1}^{+}b=\alpha_{0}^{+}\alpha_{2}^{+}c$,
$\alpha_{1}^{+}(\alpha_{1}a)=\alpha_{2}^{+}c$,
$\alpha_{1}^{+}(\alpha_{1}b)=\alpha_{0}^{+}c$;

  * •

$\alpha_{2}^{+}=\alpha_{2}$ on $C$.

When $a$ and $b$ belong to the same permutation cycle of $\phi$, the edge $e$
is a link and dual link in $M^{+}$; when they belong to different connected
components of $M$, the edge $e$ is a bridge of $M^{+}$. By Lemma 3,
$\mathbf{sg}(M)=\mathbf{sg}(M^{+})$ and
$\mathbf{sg}(M^{+})=\mathbf{sg}(M^{+}/e)$, whence
$\mathbf{sg}(M)=\mathbf{sg}(M^{(\,a\>b\,)})$.

To see that riffling crosses satisfying condition (2) also preserves genus and
orientability, it suffices to show that if in $M$ crosses $a$ and $b$ are
coincident with a common vertex and incident with distinct faces (condition
(2)(i)), then in $M^{(\,a\;b\,)}$ crosses $a$ and $b$ are incident with
distinct vertices and coincident with a common face (condition (1)(i));
likewise, if in $M$ crosses $a$ and $b$ are coincident with a common vertex
and common face and $\mathbf{k}(M^{(\,a\>b\,)})>\mathbf{k}(M)$ (condition
(2)(ii)), then in $M^{(\,a\;b\,)}$ crosses $a$ and $b$ are incident with
vertices and faces in different connected components (condition (1)(ii)). For
then we have,
$\mathbf{sg}(M^{(\,a\>b\,)})=\mathbf{sg}\large((M^{(\,a\>b\,)})^{(\,a\>b\,)}\large)$,
and the result follows as $(M^{(\,a\;b\,)})^{(\,a\;b\,)}=M$.

It remains then to establish the effect of riffling crosses $a,b$ on the
vertex and face permutations of $M$ under condition (2); as riffling $a,b$
again returns $M^{(\,a\>b\,)}$ to the original map $M$, it suffices to
establish the effect of riffling on $\tau$ and $\phi$ under condition (1). (We
choose this direction as it will be useful for clarifying what is involved in
the key operation of vertex gluing, defined in Definition 8 below and
illustrated in Figure 3 with the same notation as here.)

Suppose first condition (1)(i) that the crosses $a$ and $b$ are incident with
distinct vertices $u$ and $v$, and coincident with a common face $z$ in $M$.
The pair of face permutation cycles associated with $z$ takes the form

$\phi_{z}=(\;\;a\;\;\;\mathbf{x}\;\;\;b\;\;\;\mathbf{y}\;\;)\;(\;\;\alpha_{0}\overline{\mathbf{x}}\;\;\;\alpha_{0}a\;\;\;\alpha_{0}\overline{\mathbf{y}}\;\;\;\alpha_{0}b\;\;),$

and the pairs of vertex permutation cycles associated with $u$ and $v$ take
the form

$\tau_{u}=(\;\;a\;\;\;\mathbf{u}\;\;)\;(\;\;\alpha_{2}\overline{\mathbf{u}}\;\;\;\alpha_{2}a\;\;)\;\quad\mbox{and}\quad\;\tau_{v}=(\;\;b\;\;\;\mathbf{v}\;\;)\;(\;\;\alpha_{2}\overline{\mathbf{v}}\;\;\;\alpha_{2}b\;\;),$

for (possibly empty) cross sequences $\mathbf{x},\mathbf{y},\mathbf{u}$ and
$\mathbf{v}$.

After riffling $a$ and $b$, the face $z$ of $M$ is split into two faces $x,y$
and vertices $u$ and $v$ are merged into a single vertex $w$; in terms of the
vertex permutation $\widetilde{\tau}=\widetilde{\alpha}_{1}\alpha_{2}$ and
face permutation $\widetilde{\phi}=\widetilde{\alpha}_{1}\alpha_{0}$ of the
map $M^{(\,a\>b\,)}\equiv(C,\alpha_{0},\widetilde{\alpha}_{1},\alpha_{2})$
obtained upon merging $u$ and $v$ through $z$,

$\widetilde{\phi}_{x}=(\;\;a\;\;\;\mathbf{x}\;\;)\;(\;\;\alpha_{0}\overline{\mathbf{x}}\;\;\;\alpha_{0}a\;\;)\;\quad\mbox{and}\quad\;\widetilde{\phi}_{y}=(\;\;b\;\;\;\mathbf{y}\;\;)\;(\;\;\alpha_{0}\overline{\mathbf{y}}\;\;\;\alpha_{0}b\;\;),$

and

$\widetilde{\tau}_{w}=(\;\;a\;\;\;\mathbf{u}\;\;\;b\;\;\;\mathbf{v}\;\;)\;(\;\;\alpha_{2}\overline{\mathbf{u}}\;\;\;\alpha_{2}a\;\;\;\alpha_{2}\overline{\mathbf{v}}\;\;\;\alpha_{2}b\;\;).$

On other crosses we have $\widetilde{\tau}=\tau$ and $\widetilde{\phi}=\phi$.
Thus, riffling $a,b$ consists in merging the vertices $u$ and $v$ into a
single vertex $w$ while splitting the common face $z$ into faces $x$ and $y$.
The crosses $a,b$ now satisfy condition (i) of part (2). Riffling $a,b$ again
returns us to condition (i) of part (1).

Suppose now condition (1)(ii) that crosses $a,b$ are incident with vertices
$u,v$ and faces $x,y$ that are in different connected components of $M$. Here
we have

$\tau_{u}=(\;\;a\;\;\;\mathbf{u}\;\;)\;(\;\;\alpha_{2}\overline{\mathbf{u}}\;\;\;\alpha_{2}a\;\;)\;\quad\mbox{and}\quad\;\tau_{v}=(\;\;b\;\;\;\mathbf{v}\;\;)\;(\;\;\alpha_{2}\overline{\mathbf{v}}\;\;\;\;\;\alpha_{2}b\;\;),$

and

$\phi_{x}=(\;\;a\;\;\;\mathbf{x}\;\;)\;(\;\;\alpha_{0}\overline{\mathbf{x}}\;\;\;\alpha_{0}a\;\;)\;\quad\mbox{and}\quad\;\phi_{y}=(\;\;b\;\;\;\mathbf{y}\;\;)\;(\;\;\alpha_{0}\overline{\mathbf{y}}\;\;\;\alpha_{0}b\;\;),$

for (possibly empty) cross sequences $\mathbf{x},\mathbf{y},\mathbf{u}$ and
$\mathbf{v}$. Then, the result of merging $u$ and $v$ into a single vertex
$w$, along with $x$ and $y$ into a single face $z$, is to produce the map
$M^{(\,a\>b\,)}\equiv(C,\alpha_{0},\widetilde{\alpha}_{1},\alpha_{2})$ in
which

$\widetilde{\tau}_{w}=(\;\;\mathbf{u}\;\;\;a\;\;\;\mathbf{v}\;\;\;b\;\;)\;(\;\;\alpha_{2}a\;\;\;\alpha_{2}\overline{\mathbf{u}}\;\;\;\alpha_{2}b\;\;\;\alpha_{2}\overline{\mathbf{v}}\;\;).$
$\widetilde{\phi}_{z}=(\;\;a\;\;\;\mathbf{x}\;\;\;b\;\;\;\mathbf{y}\;\;)\;(\;\;\alpha_{0}\overline{\mathbf{x}}\;\;\;\alpha_{0}a\;\;\;\alpha_{0}\overline{\mathbf{y}}\;\;\;\alpha_{0}b\;\;).$

The crosses $a,b$ now satisfy condition (ii) of part (2). Riffling $a,b$ again
returns us to condition (ii) of part (1). ∎

Condition (1) in Lemma 7 under which genus and orientability are preserved by
riffling crosses features in our definition of vertex gluing; see Figure 3.
(The inverse operation to vertex gluing of riffling crosses under condition
(2), which splits a vertex while preserving genus and orientability, will
feature later in Section 4.2.)

######  Definition 8.

Let $a,b$ be crosses of a map $M$ such that either

  1. (i)

$a$ and $b$ are coincident with a face $z$ while $a$ is incident with a vertex
$u$ and $b$ is incident with a different vertex $v$; or

  2. (ii)

$a,b$ are incident with vertices $u,v$ and faces $x,y$ belonging to different
connected components.

The map obtained from $M$ by gluing vertices $u$ and $v$, by (i) splitting
face $z$ or by (ii) merging faces $x$ and $y$, is the map $M^{(\,a\;b\,)}$
obtained from $M$ by riffling $a$ and $b$.

In case either $u$ or $v$ is an isolated vertex, gluing vertices $u$ and $v$
is simply the deletion of the isolated vertex (if both are isolated, then
either is chosen arbitrarily to be deleted).

Figure 3: Riffling the crosses $a$ and $b$ to obtain the map $M^{(\,a\>b\,)}$;
this is the map that results from gluing distinct vertices $u$ and $v$, whose
incident crosses $a$ and $b$ are: (i) coincident with a face $z$, (ii)
incident with different faces $x,y$ in different connected components.

The effect of vertex gluing on the vertex and face permutations of $M$ is
given explicitly at the end of the proof of Lemma 7 above.

Having now arrived at a formal definition of vertex gluing – an operation of
vertex identification in maps that preserves genus and orientability – we
finish this section by establishing some of its properties relevant to the
sequel. From Lemma 9 to Lemma 11, we establish that vertex gluing commutes
with deletion of a dual link or bridge. Lemma 14 tells us that permuting the
order of a sequence of vertex gluings gives another sequence of vertex
gluings, which by Lemma 13 results in the same map.

######  Lemma 9.

If
$e\equiv(\;\;c\;\;\;\alpha_{0}\alpha_{2}c\;\;)\;(\;\;\alpha_{0}c\;\;\;\alpha_{2}c\;\;)$
is an edge of $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$ and $a,b$ are
crosses of $M$ such that
$\\{a,b,\alpha_{1}a,\alpha_{1}b\\}\cap\\{c,\alpha_{0}c,\alpha_{2}c,\alpha_{0}\alpha_{2}c\\}=\emptyset$,
then

$(M\backslash e)^{(\,a\>b\,)}=M^{(\,a\>b\,)}\backslash
e,\quad\mbox{and}\quad(M/e)^{(\,a\>b\,)}=M^{(\,a\>b\,)}/e.$

###### Proof.

We prove the identity for deletion of $e$; the proof for its contraction is
similar. The map
$M^{(\,a\>b\,)}\equiv(C,\alpha_{0},\widetilde{\alpha}_{1},\alpha_{2})$ has
involution $\widetilde{\alpha}_{1}$ equal to $\alpha_{1}$ conjugated by
$(\;\;a\;\;\;b\;\;)$. The map $M\backslash
e\equiv(C^{\prime},\alpha_{0}^{\prime},\alpha_{1}^{\prime},\alpha_{2}^{\prime})$
has
$C^{\prime}=C\setminus\\{c,\alpha_{0}c,\alpha_{2}c,\alpha_{0}\alpha_{2}c\\}$,
and $\alpha_{0}^{\prime}=\alpha_{0}$ and $\alpha_{2}^{\prime}=\alpha_{2}$ on
$C^{\prime}$. To obtain $\alpha_{1}^{\prime}$ from $\alpha_{1}$ in terms of
its disjoint cycle decomposition (product of transpositions) consider the (at
most four) transpositions of $\alpha_{1}$ containing a cross from edge $e$. We
first describe how the transpositions of $\alpha_{1}^{\prime}$ are obtained
from those of $\alpha_{1}$; after this we describe the conditions under which
pairs of empty cycles are added to $\alpha_{1}^{\prime}$ (representing new
isolated vertices).

If the crosses of $e$ are in four distinct transpositions of $\alpha_{1}$,
after removing them, merge together into a single transposition the crosses
that were paired with $c$ and $\alpha_{2}c$, and likewise those that were
paired with $\alpha_{0}c$ and $\alpha_{0}\alpha_{2}c$. If there are three
transpositions containing crosses from $e$, then there is one transposition
containing two crosses of $e$, and two containing just one cross from $e$;
after removing the crosses of $e$, merge together the remaining non-empty
cycles to make a single transposition in place of the orginal two. Finally, if
there are just two transpositions containing crosses from $e$, then the
transpositions of $\alpha_{1}^{\prime}$ are simply obtained by removing these
transpositions.

The conditions under which pairs of empty cycles are added to
$\alpha_{1}^{\prime}$ are as follows. If $\alpha_{1}c=\alpha_{2}c$, then a
pair of empty cycles is added to represent the isolated vertex that results;
likewise, if $\alpha_{1}\alpha_{0}c=\alpha_{0}\alpha_{2}c$ then a pair of
empty cycles is added to represent the isolated vertex that results. (This
corresponds to deleting a link with endpoint(s) of degree one.) If
$\alpha_{1}c=\alpha_{0}c$ and $\alpha_{1}\alpha_{2}c=\alpha_{2}\alpha_{0}c$,
then a single pair of empty cycles is added. (This corresponds to deleting a
non-twisted loop, and a single new isolated vertex is obtained.) If
$\alpha_{1}c=\alpha_{2}\alpha_{0}c$ and $\alpha_{1}\alpha_{2}c=\alpha_{0}c$,
then a single pair of empty cycles is added. (This corresponds to deleting a
twisted loop, and a single new isolated vertex is obtained.)

We thus see that the involution $\alpha_{1}^{\prime}$ of $M\backslash e$
differs from $\alpha_{1}$ only on
$\\{c,\alpha_{0}c,\alpha_{2}c,\alpha_{0}\alpha_{2}c\\}\cup\\{\alpha_{1}c,\alpha_{1}\alpha_{0}c,\alpha_{1}\alpha_{2}c,\alpha_{1}\alpha_{0}\alpha_{2}c\\}$.

Having now seen how deletion of an edge is defined in terms of the involution
$\alpha_{1}$,444For contraction, the effect on $\alpha_{1}$ is the same as
described for deletion with the roles of $\alpha_{0}$ and $\alpha_{2}$
switched. (Contraction produces isolated vertices for non-twisted loops, where
$\alpha_{1}c=\alpha_{0}c$ or $\alpha_{1}\alpha_{2}c=\alpha_{0}\alpha_{2}c$.)
we observe that the hypothesis that
$\\{a,b,\alpha_{1}a,\alpha_{1}b\\}\cap\\{c,\alpha_{0}c,\alpha_{2}c,\alpha_{0}\alpha_{2}c\\}=\emptyset$
implies further that
$\\{a,b,\alpha_{1}a,\alpha_{1}b\\}\cap\\{\alpha_{1}c,\alpha_{1}\alpha_{0}c,\alpha_{1}\alpha_{2}c,\alpha_{1}\alpha_{0}\alpha_{2}c\\}=\emptyset$
(by applying the involution $\alpha_{1}$ to the two sets in the intersection).
As deleting $e$ and riffling $a,b$ thus change $\alpha_{1}$ on disjoint sets
of crosses, and they both preserve $\alpha_{0}$ and $\alpha_{2}$ on
$C^{\prime}$, these operations commute. ∎

######  Corollary 10.

If
$e\equiv(\;\;c\;\;\;\alpha_{0}\alpha_{2}c\;\;)\>(\;\;\alpha_{0}c\;\;\;\alpha_{2}c\;\;)$
is a dual link or bridge of
$M\equiv(C,\allowbreak\alpha_{0},\allowbreak\alpha_{1},\allowbreak\alpha_{2})$
and $a,b$ are crosses of $M$ such that
$\\{a,b,\alpha_{1}a,\alpha_{1}b\\}\cap\\{c,\alpha_{0}c,\alpha_{2}c,\alpha_{0}\alpha_{2}c\\}=\emptyset$,
then the vertex gluing of $M$ represented by riffling $a,b$ is also a vertex
gluing of $M\backslash e$, again represented by riffling $a,b$.

###### Proof.

As $(M\backslash e)^{(\,a\>b\,)}=M^{(\,a\>b\,)}\backslash e$ by Lemma 9, we
only need to check that crosses $a,b$ incident with distinct vertices and
either coincident with a common face in $M$ or in different connected
components of $M$ are also coincident with a common face in $M\backslash e$ or
lie in different connected components of $M\backslash e$.

The effect of deleting a dual link $e$ incident with faces $x^{\prime}$ and
$y^{\prime}$ in $M$ is to merge $x^{\prime}$ and $y^{\prime}$ into a single
face $z^{\prime}$. If $a,b$ are coincident with a common face $z$ of $M$, then
the same is true in $M\backslash e$ (the same face $z$ if
$z\not\in\\{x^{\prime},y^{\prime}\\}$, the merging of $x^{\prime}$ and
$y^{\prime}$ if $z\in\\{x^{\prime},y^{\prime}\\}$). If $a,b$ belong to
different connected components of $M$ and are incident with faces $x,y$ in
$M$, then they belong to different connected components in $M\backslash e$ and
are incident with the same faces $x,y$ in $M\backslash e$ as they are in $M$.

Deleting a bridge $e$ incident with face $z^{\prime}$ in $M$ splits
$z^{\prime}$ into two faces $x^{\prime},y^{\prime}$ belonging to different
connected components. If $a,b$ are coincident with a common face $z$ of $M$,
then the same is true in $M\backslash e$ when $z\neq z^{\prime}$; if
$z=z^{\prime}$, crosses $a,b$ are either coincident with common face
$x^{\prime}$ or with common face $y^{\prime}$ in $M\backslash e$, or in
different connected components incident with faces $x^{\prime}$ and
$y^{\prime}$. If $a,b$ belong to different connected components of $M$ and are
incident with faces $x,y$ in $M$, then they belong to different connected
components in $M\backslash e$ and are incident with the same faces $x,y$ in
$M\backslash e$ as they are in $M$ unless $\\{x,y\\}\cap\\{z\\}\neq\emptyset$,
in which case the face in the component of $M$ containing $e$, say $x=z$
containing $a$, is split into two faces, one of which contains $a$ (however,
the statement regarding the fact that $a,b$ belong to different connected
components of $M\setminus e$ remains valid). ∎

Corollary 10 can be extended to Lemma 11 below to accommodate deletion of any
dual link or bridge, which will allow us in Corollary 12 to induce, from a
vertex gluing of $M$, a corresponding vertex gluing of a submap of the same
genus and orientability.

######  Lemma 11.

Let $e$ be either a dual link or a bridge with no endpoint of degree one of a
map $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$. Let $a,b$ be crosses of $M$
incident with distinct vertices and either coincident with a common face or in
different connected components of $M$. Then there are uniquely defined crosses
$a^{\prime},b^{\prime}\in C$ such that $(M^{(\,a\>b\,)})\backslash
e=(M\backslash e)^{(\,a^{\prime}\>b^{\prime}\,)}$. In particular, to the
vertex gluing of $M$ represented by riffling $a,b$ corresponds a vertex gluing
of $M\backslash e$ represented by riffling $a^{\prime},b^{\prime}$.

###### Proof.

Let
$e\equiv(\;\;c\;\;\;\alpha_{0}\alpha_{2}c\;\;)\>(\;\;\alpha_{0}c\;\;\;\alpha_{2}c\;\;)$.
When
$\\{a,b,\alpha_{1}a,\alpha_{1}b\\}\cap\\{c,\alpha_{0}c,\alpha_{2}c,\alpha_{0}\alpha_{2}c\\}=\emptyset$,
by Corollary 10, we can take $a^{\prime}=a,b^{\prime}=b$.

If $e$ is a dual link then $a$ and $b$ cannot both belong to
$\\{c,\alpha_{0}c,\alpha_{2}c,\alpha_{0}\alpha_{2}c\\}$ because they are
coincident with a common face (preventing $b=\alpha_{0}a$) and, as $e$ is a
dual link, $c,\alpha_{0}c$ belong to a different face to
$\alpha_{2}c,\alpha_{0}\alpha_{2}c$ (preventing $b$ from being one of these
crosses). Suppose then, without loss of generality, that $a=c$ is incident
with face $x$ of $M$ and
$b\not\in\\{c,\alpha_{0}c,\alpha_{2}c,\alpha_{0}\alpha_{2}c\\}$ is either a
cross coincident with $a$ on face $x$ or a cross belonging to a different
connected component of $M$. If we set $a^{\prime}=\alpha_{1}\alpha_{2}a=\tau
a$ then $(M^{(\,a\>b\,)})\backslash e=(M\backslash e)^{(\,a^{\prime}\>b\,)}$.

Now suppose that $e$ is a bridge incident with face $z$ and that $a=c$.
Possibly $b=\alpha_{0}\alpha_{2}c$, a cross coincident with $a$ on face $z$,
but in any event $b\not\in\\{\alpha_{0}c,\alpha_{2}c\\}$. When
$b\neq\alpha_{0}\alpha_{2}c$, the same choice of
$a^{\prime}=\alpha_{1}\alpha_{2}a$ gives $(M^{(\,a\>b\,)})\backslash
e=(M\backslash e)^{(\,a^{\prime}\>b\,)}$, unless $a$ is incident with an
endpoint of $e$ of degree one. When $b=\alpha_{0}\alpha_{2}c$, crosses
$a^{\prime}=\alpha_{1}\alpha_{2}a$ and $b^{\prime}=\alpha_{1}\alpha_{2}b$
belong to different connected components of $M\backslash e$, the edge $e$ is a
loop in $M^{(\,a\>b\,)}$, and we have $(M^{(\,a\>b\,)})\backslash
e=(M\backslash e)^{(\,a^{\prime}\>b^{\prime}\,)}=M/e$.

In all cases, the cross $a^{\prime}$ is equal to $a$ when
$a\not\in\\{c,\alpha_{0}c,\alpha_{2}c,\alpha_{0}\alpha_{2}c\\}$ and to $\tau
a$ when $a\in\\{c,\alpha_{0}c,\alpha_{2}c,\alpha_{0}\alpha_{2}c\\}$; and
likewise $b^{\prime}$ is set equal to $b$ or $\tau b$ according as it does not
or does belong to the crosses of $e$. ∎

The following corollary gives a way to restrict a sequence of vertex gluings
to a spanning submap, and will be used in Section 3.3 to define the
restriction of a map homomorphism to a submap.

######  Corollary 12.

Let $M\backslash A$ be a spanning submap of $M$ such that
$\mathbf{sg}(M\backslash A)=\mathbf{sg}(M)$, and let $a,b$ be crosses of $M$
incident with distinct vertices $u,v$ and either coincident with a common face
or in different connected components. If neither $u$ nor $v$ are isolated
vertices in $M\backslash A$, then there are crosses $a^{\prime},b^{\prime}$ of
$M\backslash A$ such that $M^{(\,a\>b\,)}\backslash A=(M\backslash
A)^{(\,a^{\prime}\>b^{\prime}\,)}$.

###### Proof.

Lemma 11 and induction yield the result as any spanning submap of the same
signed genus as $M$ is, by Lemma 3(i), obtained by a sequence of deletions of
dual links or bridges. ∎

The following lemma records the effect of switching the order in which two
riffles are composed.

######  Lemma 13.

For two pairs of distinct crosses $a,b$ and $a^{\prime},b^{\prime}$ of a map
$M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$, the following statements hold:

  1. (i)

If $a,b,a^{\prime},b^{\prime}$ are distinct, then
$(M^{(\,a\>b\,)})^{(\,a^{\prime}\>b^{\prime}\,)}=(M^{(\,a^{\prime}\>b^{\prime}\,)})^{(\,a\>b\,)}$,
and the same identity holds with $(\;\;\alpha_{1}a\;\;\;\alpha_{1}b\;\;)$ in
place of $(\;\;a\;\;\;b\;\;)$ or with
$(\;\;\alpha_{1}a^{\prime}\;\;\;\alpha_{1}b^{\prime}\;\;)$ in place of
$(\;\;a^{\prime}\;\;\;b^{\prime}\;\;)$.

  2. (ii)

If $a=a^{\prime}$ and $b\neq b^{\prime}$, then
$(M^{(\,a\>b\,)})^{(\,a\>b^{\prime}\,)}=(M^{(\,a\>b^{\prime}\,)})^{(\,\alpha_{1}a\>\;\alpha_{1}b\,)}$,
and the same identity holds with $(\;\;\alpha_{1}a\;\;\;\alpha_{1}b\;\;)$ in
place of $(\;\;a\;\;\;b\;\;)$ or with
$(\;\;\alpha_{1}a\;\;\;\alpha_{1}b^{\prime}\;\;)$ in place of
$(\;\;a\;\;\;b^{\prime}\;\;)$.

  3. (iii)

If $a=a^{\prime}$ and $b=b^{\prime}$, then $(M^{(\,a\>b\,)})^{(\,a\>b\,)}=M$,
and the same identity holds with either transposition $(\;\;a\;\;\;b\;\;)$
(possibly both) replaced by $(\;\;\alpha_{1}a\;\;\;\alpha_{1}b\;\;)$.

###### Proof.

Suppose first that no cross among
$a^{\prime},b^{\prime},\alpha_{1}a^{\prime},\alpha_{1}b^{\prime}$ is a cross
among $a,b,\alpha_{1}a,\alpha_{1}b$. Then,
$(\;\;a\;\;\;b\;\;)\;\;(\;\;a^{\prime}\;\;\;b^{\prime}\;\;)=(\;\;a^{\prime}\;\;\;b^{\prime}\;\;)\;\;(\;\;a\;\;\;b\;\;)$,
and thus conjugating $\alpha_{1}$ by $(\;\;a\;\;\;b\;\;)$ and then by
$(\;\;a^{\prime}\;\;\;b^{\prime}\;\;)$ gives the same permutation as when
conjugating first by $(\;\;a^{\prime}\;\;\;b^{\prime}\;\;)$ and then by
$(\;\;a\;\;\;b\;\;)$. Hence,
$(M^{(\,a\>b\,)})^{(\,a^{\prime}\>b^{\prime}\,)}=(M^{(\,a^{\prime}\>b^{\prime}\,)})^{(\,a\>b\,)}$,
which proves (i). The same argument shows that the identity holds with
$\alpha_{1}a,\alpha_{1}b$ replacing $a,b$ or with
$\alpha_{1}a^{\prime},\alpha_{1}b^{\prime}$ replacing $a^{\prime},b^{\prime}$.

Suppose now that $a=a^{\prime}$ and $b\neq b^{\prime}$. The involution

$\alpha_{1}=(\;\;a\;\;\;\alpha_{1}a\;\;)\;\;(\;\;b\;\;\;\alpha_{1}b\;\;)\;\;(\;\;b^{\prime}\;\;\;\alpha_{1}b^{\prime}\;\;)\>\dots$
(4)

after conjugating by $(\;\;a\;\;\;b^{\prime}\;\;)$ or by
$(\;\;\alpha_{1}a\;\;\;\alpha_{1}b^{\prime}\;\;)$ becomes
$(\;\;a\;\;\;\alpha_{1}b^{\prime}\;\;)\;\;(\;\;b\;\;\;\alpha_{1}b\;\;)\;\;(\;\;b^{\prime}\;\;\;\alpha_{1}a\;\;)\>\dots$
Then, conjugating by $(\;\;\alpha_{1}a\;\;\;\alpha_{1}b\;\;)$ gives

$(\;\;a\;\;\;\alpha_{1}b^{\prime}\;\;)\;\;(\;\;b\;\;\;\alpha_{1}a\;\;)\;\;(\;\;b^{\prime}\;\;\;\alpha_{1}b\;\;)\>\dots$
(5)

Conjugating now the involution $\alpha_{1}$ in (4) by $(\;\;a\;\;\;b\;\;)$ or
by $(\;\;\alpha_{1}a\;\;\;\alpha_{1}b\;\;)$ gives

$(\;\;b\;\;\;\alpha_{1}a\;\;)\;\;(\;\;a\;\;\;\alpha_{1}b\;\;)\;\;(\;\;b^{\prime}\;\;\;\alpha_{1}b^{\prime}\;\;)\>\dots,$

and then conjugating by $(\;\;a\;\;\;b^{\prime}\;\;)$ gives
$(\;\;b\;\;\;\alpha_{1}a\;\;)\;\;(\;\;b^{\prime}\;\;\;\alpha_{1}b\;\;)\;\;(\;\;a\;\;\;\alpha_{1}b^{\prime}\;\;)\>\dots,$
which is the same involution as (5). This establishes (ii).

Finally, when $a=a^{\prime}$ and $b=b^{\prime}$, conjugating $\alpha_{1}$ by
$(\;\;a\;\;\;b\;\;)$ and then again by $(\;\;a\;\;\;b\;\;)$ is to conjugate by
the product of transpositions $(\;\;a\;\;\;b\;\;)\;\;(\;\;a\;\;\;b\;\;)$,
equal to the identity permutation. This yields (iii). ∎

Before stating the next lemma, we define a notion needed for its proof and
used further in Section 4.2 below. Distinct crosses
$a,b,a^{\prime},b^{\prime}$ are interlacing in a cycle of crosses $\gamma$ if
$\gamma=(\;\;a\;\;\;\mathbf{x}\;\;\;a^{\prime}\;\;\;\allowbreak\mathbf{y}\;\;\;\allowbreak
b\;\;\;\allowbreak\mathbf{z}\;\;\;b^{\prime}\;\;\;\mathbf{w}\;\;)$ or
$\gamma=(\;\;a\;\;\;\mathbf{x}\;\;\;b^{\prime}\;\;\;\mathbf{y}\;\;\;b\;\;\;\mathbf{z}\;\;\;a^{\prime}\;\;\;\mathbf{w}\;\;)$,
where $\mathbf{x},\mathbf{y},\mathbf{z}$ and $\mathbf{w}$ are (possibly empty)
sequences of crosses.

######  Lemma 14.

Let $a,b$ and $a^{\prime},b^{\prime}$ be two pairs of distinct crosses of a
map $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$, and let $M^{(\,a\>b\,)}$ be
a vertex gluing of $M$ and $(M^{(\,a\>b\,)})^{(\,a^{\prime}\>b^{\prime}\,)}$ a
vertex gluing of $M^{(\,a\>b\,)}$. Then, either

  1. (i)

$M^{(\,a^{\prime}\>b^{\prime}\,)}$ is a vertex gluing of $M$ and
$(M^{(\,a^{\prime}\>b^{\prime}\,)})^{(\,a\>b\,)}$ is a vertex gluing of
$M^{(\,a^{\prime}\>b^{\prime}\,)}$, and
$(M^{(\,a\>b\,)})^{(\,a^{\prime}\>b^{\prime}\,)}=\allowbreak(M^{(\,a^{\prime}\>b^{\prime}\,)})^{(\,a\>b\,)}$,
or

  2. (ii)

$M^{(\,\alpha_{1}a^{\prime}\>\alpha_{1}b^{\prime}\,)}$ is a vertex gluing of
$M$ and $(M^{(\,\alpha_{1}a^{\prime}\>\alpha_{1}b^{\prime}\,)})^{(\,a\>b\,)}$
is a vertex gluing of $M^{(\,\alpha_{1}a^{\prime}\>\alpha_{1}b^{\prime}\,)}$,
and
$(M^{(\,a\>b\,)})^{(\,a^{\prime}\>b^{\prime}\,)}=(M^{(\,\alpha_{1}a^{\prime}\>\alpha_{1}b^{\prime}\,)})^{(\,a\>b\,)}$,
or

  3. (iii)

$M^{(\,a^{\prime}\>b^{\prime}\,)}$ is a vertex gluing of $M$ and
$(M^{(\,a^{\prime}\>b^{\prime}\,)})^{(\,\alpha_{1}a\>\alpha_{1}b\,)}$ is a
vertex gluing of $M^{(\,a^{\prime}\>b^{\prime}\,)}$, and
$(M^{(\,a\>b\,)})^{(\,a^{\prime}\>b^{\prime}\,)}=(M^{(\,a^{\prime}\>b^{\prime}\,)})^{(\,\alpha_{1}a\>\alpha_{1}b\,)}$.

###### Proof.

The final equalities of statements (i), (ii) and (iii) follow from Lemma 13.
To establish the remainder of the lemma we shall show that if $a,b$ are either

  1. (h1)

incident with distinct vertices and coincident with a common face of $M$, or

  2. (h2)

incident with vertices and faces in different connected components of $M$,

and $a^{\prime},b^{\prime}$ are either

  1. (h1’)

incident with distinct vertices and coincident with a common face of
$M^{(\,a\>b\,)}$, or

  2. (h2’)

incident with vertices and faces in different connected components of
$M^{(\,a\>b\,)}$,

then $a^{\prime},b^{\prime}$ are either

  1. (c1)

incident with distinct vertices and coincident with a common face of $M$, or

  2. (c2)

incident with vertices and faces in different connected components of $M$,

and $a,b$ are either

  1. (c1’)

incident with distinct vertices and coincident with a common face of
$M^{(\,a^{\prime}\>b^{\prime}\,)}$, or

  2. (c2’)

incident with vertices and faces in different connected components of
$M^{(\,a^{\prime}\>b^{\prime}\,)}$,

with the appropriate changes for cases (ii) and (iii) of the statement: For
(ii) we replace $a^{\prime}$ by $\alpha_{1}a^{\prime}$ and $b^{\prime}$ by
$\alpha_{1}b^{\prime}$ in (c1), (c2), (c1’) and (c2’); for (iii) we replace
$a$ by $\alpha_{1}a$ and $b$ by $\alpha_{1}b$ in (c1), (c2), (c1’) and (c2’).

We take in turn the four cases according to the position of crosses $a,b$ in
$M$ and the position of $a^{\prime},b^{\prime}$ in $M^{(\,a\>b\,)}$. We notice
that cases (ii) and (iii) only occur in the first case of the proof below.

_Case(h1) and (h1’):_ Riffling $a,b$ in $M$ splits the face $z$ in $M$
containing $a,b$ into two faces $x,y$, the first containing $a$ and the second
$b$. By (h1’), there is a face $z^{\prime}$ in $M^{(\,a\>b\,)}$ containing
$a^{\prime},b^{\prime}$.

If $z^{\prime}\neq x$ and $z^{\prime}\neq y$, then the face $z^{\prime}$ is
also a face in $M$, and we obtain (c1) (for if the vertices of $a^{\prime}$
and $b^{\prime}$ are distinct in $M^{(\,a\>b\,)}$, then they are also distinct
in $M$ as, since we are performing a vertex gluing, there is a surjective
mapping from the vertices of $M$ onto the vertices of $M^{(\,a\>b\,)}$). Now,
$a$ and $b$ are also coincident with the same face in
$M^{(\,a^{\prime}\>b^{\prime}\,)}$, by the assumption that $z^{\prime}\neq x$
and $z^{\prime}\neq y$ and (h1’); furthermore, they are also incident with
distinct vertices in $M^{(\,a^{\prime}\>b^{\prime}\,)}$ as we have just glued
the vertex incident with $a^{\prime}$ and the vertex incident with
$b^{\prime}$, and if the two distinct vertices incident with $a$ and $b$ in
$M$ now become the same in $M^{(\,a^{\prime}\>b^{\prime}\,)}$, this means that
they were also glued together in $M^{(\,a\>b\,)}$, thus contradicting the
assumption (h1’). This shows (c1’) as stated.

If $z^{\prime}=x$ (the case $z^{\prime}=y$ is argued similarly), then we
conclude that $\\{a,b,a^{\prime},b^{\prime}\\}$ are all incident with the same
face $z$ in $M$. Now, the condition (h1’) implies that
$\\{a,b\\}\neq\\{a^{\prime},b^{\prime}\\}$, for otherwise, $a^{\prime}$ and
$b^{\prime}$ would lie in two different faces, contradicting (h1’). Consider
the cycle of crosses $\gamma=(\;\;a\;\;\;\alpha_{0}a\;\;\;\phi
a\;\;\;\alpha_{0}\phi a\;\;\;\cdots\;\;\;\alpha_{1}a\;\;)$ interleaving the
two permutation cycles of the face $z$ (one of them being in its order, and
the other in reverse). Assume first that
$|\\{a,b,a^{\prime},b^{\prime}\\}|=4$, then the four crosses cannot be
interlacing in $\gamma$ for otherwise (h1’) would not hold. Then we obtain
(c1) and (c1’). Now assume that $|\\{a,b,a^{\prime},b^{\prime}\\}|=3$, say
without loss of generality that $a^{\prime}=a$. Then there are two cases for
$\gamma$, either
$\gamma_{1}=(\;\;a=a^{\prime}\;\;\;\mathbf{x}\;\;\;b\;\;\;\mathbf{y}\;\;\;b^{\prime}\;\;\;\mathbf{z}\;\;)$
or
$\gamma_{2}=(\;\;a=a^{\prime}\;\;\;\mathbf{x}\;\;\;b^{\prime}\;\;\;\mathbf{y}\;\;\;b\;\;\;\mathbf{z}\;\;)$
where $\mathbf{x},\mathbf{y},\mathbf{z}$ are non-empty sequences of
crosses.555The cyclicity of $\gamma$ and the fact that
$\\{a^{\prime},b^{\prime}\\}$ and $\\{a,b\\}$ are coincident with the face
makes the relative position of $\\{a^{\prime},\alpha_{1}a\\}$ and
$\\{b^{\prime},\alpha_{1}b^{\prime}\\}$ the same within $\gamma_{1}$ and
$\gamma_{2}$. In the first case, writing
$\mathbf{y}=(\mathbf{y}^{\prime},\alpha_{1}b^{\prime})$ and
$\mathbf{z}=(\mathbf{z}^{\prime},\alpha_{1}a^{\prime})$, we have
$\gamma_{1}=(\;\;\alpha_{1}a^{\prime}\;\;\;a\;\;\;\mathbf{x}\;\;\;b\;\;\;\mathbf{y}^{\prime}\;\;\;\alpha_{1}b^{\prime}\;\;\;b^{\prime}\;\;\;\mathbf{z}^{\prime}\;\;)$,
so $\\{\alpha_{1}a^{\prime},\alpha_{1}b^{\prime}\\}$ and $\\{a,b\\}$ are not
interlacing, and we conclude (c1) and (c1’) hold with $\alpha_{1}a^{\prime}$
and $\alpha_{1}b^{\prime}$ (thus obtaining part (ii) of the statement). In the
second case, writing $\mathbf{y}=(\mathbf{y}^{\prime},\alpha_{1}b)$ and
$\mathbf{z}=(\mathbf{z}^{\prime},\alpha_{1}a)$, we have
$\gamma_{2}=(\;\;\alpha_{1}a\;\;\;a^{\prime}\;\;\;\mathbf{x}\;\;\;b^{\prime}\;\;\;\mathbf{y}^{\prime}\;\;\;\alpha_{1}b\;\;\;b\;\;\;\mathbf{z}^{\prime}\;\;)$,
so $\\{\alpha_{1}a,\alpha_{1}b\\}$ and $\\{a^{\prime},b^{\prime}\\}$ are not
interlacing, and we have (c1) and (c1’) with $\alpha_{1}a$ and $\alpha_{1}b$
(thus obtaining part (iii) of the statement).

_Case(h1) and (h2’):_ As riffling $a,b$ in $M$ preserves connected components,
crosses $a^{\prime},b^{\prime}$ must also belong to different connected
components of $M$. Thus (c2) follows. We now show that (c1’) holds. When
riffling $a^{\prime},b^{\prime}$ in $M$, the only alteration to the connected
component of $M$ containing $a$ and $b$ may be the addition of some crosses to
one of its vertices. Thus, if $a$ and $b$ are incident with distinct vertices
in $M$, they are also incident with distinct vertices in
$M^{(\,a^{\prime}\>b^{\prime}\,)}$. The effect on the faces of this connected
component is the addition of crosses to one of its faces. Thus, if $a$ and $b$
are coincident with a single face in $M$, they are also coincident with a face
in $M^{(\,a^{\prime}\>b^{\prime}\,)}$. This shows (c1’).

_Case(h2) and (h1’):_ The riffling of $a,b$ in $M$ merges their respective
faces $x,y$ into a face $z$, with which $a,b$ are coincident in
$M^{(\,a\>b\,)}$. If the face $z^{\prime}$ of $M^{(\,a\>b\,)}$ containing
$a^{\prime}$ and $b^{\prime}$ is not equal to $z$, then
$a^{\prime},b^{\prime}$ remain coincident with this face in $M$, and we have
(c1) and (c2’). If $z^{\prime}=z$ then there are two possibilities. The first
is that $a^{\prime},b^{\prime}$ are coincident with a common face of $M$
(either $x$ or $y$), so (c1) holds; also (c2’) holds since gluing the vertices
of $a^{\prime}$ and $b^{\prime}$ in one connected component does not affect
the other connected component. The second possibility is that $a^{\prime}$ is
incident with the same face of $M$ as $a$ or $b$, say the face $x$ (but $a$
and $a^{\prime}$ are not necessarily coincident), and $b^{\prime}$ is incident
with the face $y$. In this case (c2) holds. Now, in $M^{(\,a\>b\,)}$, crosses
$a^{\prime}$ and $b^{\prime}$ are incident with the same face as $a$ and $b$,
and (h1’) implies that $a^{\prime}$ and $b^{\prime}$ are in fact coincident
with this face. Crosses $a$ and $b$ are in the same face permutation cycle as
$a^{\prime}$ and $b^{\prime}$ if both pairs $\\{a,a^{\prime}\\}$ and
$\\{b,b^{\prime}\\}$ are coincident on their faces of $M$, and different ones
if both these pairs are incident but not coincident on their faces of $M$.
(Hypothesis (h1’) prevents just one of these pairs being coincident and the
other not.) Furthermore, hypothesis (h1’) also implies that $a^{\prime}$ and
$b^{\prime}$ are incident with distinct vertices in $M^{(\,a\>b\,)}$. This
shows (c1’).

_Case(h2) and (h2’):_ Riffling $a$ and $b$ in $M$ merges the two connected
components of $a$ and $b$ into one, while the connected components of
$a^{\prime}$ and $b^{\prime}$ are not merged. Thus, the crosses
$\\{a,b,a^{\prime},b^{\prime}\\}$ span at least three connected components in
$M$. This shows that (c2) and (c2’) hold. ∎

###  3.2 Duplicate edges

If $e$ and $f$ are distinct parallel edges of $\Gamma$, then the graphs
obtained after deleting $e$ and $f$, respectively, are isomorphic via the
mapping fixing vertices and fixing all edges except $e$ and $f$, which are
swapped. Parallel edges are interchangeable when it comes to the existence of
homomorphisms: there is a homomorphism from $\Gamma\backslash e$ to a graph
$\Gamma^{\prime}$ if and only if there is a homomorphism from
$\Gamma\backslash f$ to $\Gamma^{\prime}$, and a redundancy of one of the
parallel edges in that there is a homomorphism from $\Gamma$ to
$\Gamma^{\prime}$ if and only if there is a homomorphism from
$\Gamma\backslash e$ to $\Gamma^{\prime}$. The same statements hold for
homomorphisms from the graph $\Gamma^{\prime}$ rather than to it.

There are, however, non-isomorphic maps with the same underlying graph which
differ only in the placement of parallel edges. For example, a plane 4-cycle
with a chord and an edge added in parallel to the chord, in one way bounding a
face of degree two and a face of degree three, and in the other bounding two
faces of degree three.

In order to carry over to maps the property of parallel edges in graphs being
indistinguishable when it comes to homomorphisms, we need to add a topological
constraint.

######  Definition 15.

Two edges of a map $M$ are duplicate if they are incident with a common face
of degree two.

Figure 4 illustrates different examples of duplicate and non-duplicate edges.
One can see that duplicate edges can be merged into one while remaining in the
surface of the map (much as pairs of vertices on a common face can be glued
while remaining in the surface of the map).

Figure 4: (a) Two pairs (thicker blue and dashed) of duplicate edges in a
plane map, (b) two duplicate loops in the torus (thicker edges), and a loop
that is not duplicate with the others (dashed), (c) three plane embeddings of
four loops on a vertex, the ones dashed are not duplicate with any other loop,
the non-dashed ones are duplicate loops.

######  Definition 16.

Let $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$ be a map containing crosses
$a$ and $b=\phi a$ such that
$e\equiv(\;\;a\;\;\;\alpha_{0}\alpha_{2}a\;\;)\;(\;\;\alpha_{0}a\;\;\;\alpha_{2}a\;\;)$
and
$f\equiv(\;\;b\;\;\;\alpha_{0}\alpha_{2}b\;\;)\;(\;\;\alpha_{0}b\;\;\;\alpha_{2}b\;\;)$
are duplicate edges, bounding the face
$(\;\;a\;\;\;b\;\;)\;(\;\;\alpha_{0}a\;\;\;\alpha_{0}b\;\;)$ of degree two.
The map obtained by gluing $e$ and $f$ is $M^{[\,a\;b\,]}\equiv(\mkern
1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern 1.5mu,\mkern
1.5mu\overline{\mkern-1.5mu\alpha\mkern-1.5mu}\mkern 1.5mu_{0},\mkern
1.5mu\overline{\mkern-1.5mu\alpha\mkern-1.5mu}\mkern 1.5mu_{1},\mkern
1.5mu\overline{\mkern-1.5mu\alpha\mkern-1.5mu}\mkern 1.5mu_{2})$, in which

  * •

$\mkern 1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern
1.5mu=C\backslash\\{a,\alpha_{0}a,b,\alpha_{0}b\\}$;

  * •

$\mkern 1.5mu\overline{\mkern-1.5mu\alpha\mkern-1.5mu}\mkern
1.5mu_{0}=\alpha_{0}$ and $\mkern
1.5mu\overline{\mkern-1.5mu\alpha\mkern-1.5mu}\mkern 1.5mu_{1}=\alpha_{1}$ on
$\mkern 1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern 1.5mu$;

  * •

$\mkern 1.5mu\overline{\mkern-1.5mu\alpha\mkern-1.5mu}\mkern
1.5mu_{2}=\alpha_{2}$ on $\mkern
1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern
1.5mu\backslash\\{\alpha_{2}a,\alpha_{0}\alpha_{2}a,\alpha_{2}b,\alpha_{0}\alpha_{2}b\\}$,
and

$\mkern 1.5mu\overline{\mkern-1.5mu\alpha\mkern-1.5mu}\mkern
1.5mu_{2}(\alpha_{2}a)=\alpha_{0}\alpha_{2}b,\quad\mkern
1.5mu\overline{\mkern-1.5mu\alpha\mkern-1.5mu}\mkern
1.5mu_{2}(\alpha_{0}\alpha_{2}a)=\alpha_{2}b.$

Equivalently, we obtain $M^{[\,a\;b\,]}$ from $M$ by preserving the three
involutions and setting $\alpha_{0}\alpha_{2}b\leftarrow a$ and
$\alpha_{0}\alpha_{2}a\leftarrow b$ (so that
$\alpha_{2}b\leftarrow\alpha_{0}a$ and $\alpha_{2}a\leftarrow\alpha_{0}b$).

######  Remark 17.

The map $M^{[\,a\;b\,]}$ given by Definition 16 is isomorphic to $M\backslash
f$ upon setting $\alpha_{0}\alpha_{2}b\leftarrow a$,
$\alpha_{2}b\leftarrow\alpha_{0}a$, and to $M\backslash e$ upon setting
$\alpha_{0}\alpha_{2}a\leftarrow b$, $\alpha_{2}a\leftarrow\alpha_{0}b$.

Definition 16 extends to pairs of edges $e,f$ that lie on a common face of
larger degree, or that belong to different connected components, but we shall
only apply it to pairs of edges that are duplicate: the more general operation
of gluing $e$ and $f$ can be defined as a composition of two vertex gluings
(if $e$ and $f$ share no endpoint) or one vertex gluing (if $e$ and $f$ share
a single endpoint) and a duplicate edge gluing.

Edges that are duplicate in $M$ are incident with a common vertex of degree
two in $M^{*}$. The maximal induced paths in $M^{*}$ have edge sets equal to
the equivalence classes of the relation defined on $M$ by taking the
transitive closure of the relation of being duplicate: this equivalence
relation refines that of parallel edges in the underlying graph of $M$.

######  Lemma 18.

If $e,f$ are duplicate edges in $M$, then $\mathbf{sg}(M\backslash
e)=\mathbf{sg}(M\backslash f)=\mathbf{sg}(M)$.

###### Proof.

The first equality follows by Remark 17, and the second equality by Lemma 3
(i) as duplicate edges are dual links. ∎

The following lemma tells us that duplicate edges remain duplicate under
vertex gluing (except possibly when the vertex gluing involves the face
bounded by the duplicate edges), and that gluing duplicates can be done before
or after a vertex gluing without changing the resulting map.

######  Lemma 19.

Let $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$ be a map containing crosses
$a$ and $b=\phi a$ such that
$e\equiv(\;\;a\;\;\;\alpha_{0}\alpha_{2}a\;\;)\;(\;\;\alpha_{0}a\;\;\;\alpha_{2}a\;\;)$
and
$f\equiv(\;\;b\;\;\;\alpha_{0}\alpha_{2}b\;\;)\;(\;\;\alpha_{0}b\;\;\;\alpha_{2}b\;\;)$
are duplicate edges.

Suppose that $a^{\prime},b^{\prime}$ are crosses of $M$ such that
$\\{a^{\prime},b^{\prime},\alpha_{1}a^{\prime},\alpha_{1}b^{\prime}\\}$ is
disjoint from $\\{a,\alpha_{0}a,b,\alpha_{0}b\\}$. Then $e$ and $f$ are
duplicate in $M^{(\,a^{\prime}\>b^{\prime}\,)}$ and

$(M^{[\,a\;b\,]})^{(\,a^{\prime}\>b^{\prime}\,)}=(M^{(\,a^{\prime}\>b^{\prime}\,)})^{[\,a\;b\,]}.$

###### Proof.

By the disjointedness condition on crosses
$a^{\prime},b^{\prime},\alpha_{1}a^{\prime},\alpha_{1}b^{\prime}$, riffling
$a^{\prime},b^{\prime}$ fixes $a,b,\alpha_{1}a=\alpha_{0}b$ and
$\alpha_{1}b=\alpha_{0}a$, and therefore the face of degree two
$(\;\;a\;\;\;b\;\;)\;(\;\;\alpha_{0}a\;\;\;\alpha_{0}b\;\;)$ is unchanged,
i.e. the edges $e$ and $f$ remain duplicate in
$M^{(\,a^{\prime}\>b^{\prime}\,)}$.

Riffling $a^{\prime},b^{\prime}$ fixes $\alpha_{0}$ and $\alpha_{2}$, and only
changes $\alpha_{1}$ on the four crosses
$a^{\prime},b^{\prime},\alpha_{1}a^{\prime},\alpha_{1}b^{\prime}$, which by
asssumption all belong to $\mkern
1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern
1.5mu=C\setminus\\{a,\alpha_{0}a,b,\alpha_{0}b\\}$. The map $M^{[\,a\;b\,]}$
is obtained by restricting $\alpha_{0},\alpha_{1}$ to $\mkern
1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern 1.5mu$, and restricting
$\alpha_{2}$ to $\mkern 1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern 1.5mu$
while changing its values on
$\alpha_{2}a,\alpha_{0}\alpha_{2}a,\alpha_{2}b,\alpha_{0}\alpha_{2}b$ from
$a,\alpha_{0}a,b,\alpha_{0}b$ to
$\alpha_{0}\alpha_{2}b,\alpha_{2}b,\alpha_{0}\alpha_{2}a,\alpha_{2}a$,
respectively. The involutions $\alpha_{0},\alpha_{1},\alpha_{2}$ are thus by
riffling/duplicate edge gluing affected as follows:

| riffling | duplicate edge gluing
---|---|---
$\alpha_{0}$ | fix | restrict to $\mkern 1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern 1.5mu$
$\alpha_{1}$ | change on $\\{a^{\prime},\alpha_{1}a^{\prime},b^{\prime},\alpha_{1}b^{\prime}\\}$ | restrict to $\mkern 1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern 1.5mu$
$\alpha_{2}$ | fix | restrict to $\mkern 1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern 1.5mu$ and change on $\\{\alpha_{2}a,\alpha_{0}\alpha_{2}a,\alpha_{2}b,\alpha_{0}\alpha_{2}b\\}$.

For each involution, duplicate edge gluing followed by riffling has the same
effect as riffling followed by duplicate edge gluing. (For $\alpha_{1}$, the
condition that the four crosses
$a^{\prime},b^{\prime},\alpha_{1}a^{\prime},\alpha_{1}b^{\prime}$ all belong
to $\mkern 1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern
1.5mu=C\setminus\\{a,\alpha_{0}a,b,\alpha_{0}b\\}$ is needed so that the
restriction to $\mkern 1.5mu\overline{\mkern-1.5muC\mkern-1.5mu}\mkern 1.5mu$
can be followed by the changes on
$\\{a^{\prime},b^{\prime},\alpha_{1}a^{\prime},\alpha_{1}b^{\prime}\\}$.) ∎

In a similar way to how we “remove parallel edges” of a graph while
maintaining at least one edge in each parallel class, we can glue pairs of
duplicate edges in a map iteratively until no further duplicates remain.
Duplicate edges $e,f$ of $M$ are interchangeable in the sense that there is a
isomorphism from $M\backslash e$ to $M\backslash f$ that fixes all vertices
and all edges apart from $e$ or $f$.

###  3.3 Homomorphisms

We have seen how a sequence of vertex gluings followed by a sequence of
duplicate edge gluings takes one map onto another map of the same signed
genus: the mapping induced on the underlying graphs of the maps is an
epimorphism (surjective graph homomorphism). This motivates, in particular,
the following definition of an epimorphism between maps.

######  Definition 20.

Let $M$ and $N$ be maps of the same signed genus.

An _epimorphism_ $n:M\twoheadrightarrow N$ from $M$ onto $N$ is an isomorphism
of $N$ to a map obtained from $M$ by performing a sequence of vertex gluings
and a sequence of duplicate edge gluings.

A monomorphism from $M$ into $N$ is an isomorphism from $M$ to a submap of
$N$.

In an epimorphism either sequence – of vertex gluings or of duplicate edge
gluings – may be empty. Notice that Lemmas 13, 14 and 19 together imply that
vertex gluings can be done first, followed by duplicate edge gluings, and the
order within each sequence does not matter (that edge gluings commute with
each other easily follows by interpreting it as edge deletion.)

Before giving our definition of map homomorphism, we record the following
proposition, which will be used in Section 4.

######  Proposition 21.

Let $M,M^{\prime}$ be two maps such that there exist epimorphisms
$M\twoheadrightarrow M^{\prime}$ and $M^{\prime}\twoheadrightarrow M$ (resp,.
monomorphisms $M\rightarrowtail M^{\prime}$ and $M^{\prime}\rightarrowtail
M$). Then, $M$ and $M^{\prime}$ are isomorphic.

###### Proof.

If there are epimorphisms both ways between $M$ and $M^{\prime}$, then there
can be neither vertex gluings (which reduce the number of vertices) nor
duplicate edge gluings (which reduce the number of edges). Since $M^{\prime}$
is thus obtained from $M$ by empty sequences of vertex gluings and duplicate
edge gluings, there is an isomorphism between $M^{\prime}$ and $M$.

If there are monomorphisms both ways between $M$ and $M^{\prime}$, there are
isomorphisms between $M$ and a submap of $M^{\prime}$ and between $M^{\prime}$
and a submap of $M$. As the maps are finite there is thus an isomorphism
between $M$ and $M^{\prime}$. ∎

######  Definition 22.

Let $M,M^{\prime}$ be maps of the same signed genus. A _map homomorphism_ from
$M$ to $M^{\prime}$ is a composition of an epimorphism from $M$ onto a submap
$N$ of $M^{\prime}$ and a monomorphism from $N$ into $M^{\prime}$. In symbols,
a map homomorphism $h:M\to M^{\prime}$ is the composition $m\circ n$ of an
epimorphism $n:M\twoheadrightarrow N$ and a monomorphism $m:N\rightarrowtail
M^{\prime}$.

A homomorphism from one map to another gives a graph homomorphism between
their underlying graphs: a map homomorphism can thus be regarded as a graph
homomorphism that satisfies further topological constraints specified by an
embedding of the graph as a map.

A homomorphism $h:M\to M^{\prime}$ given by the composition $h=m\circ n$, has
image, denoted by $h(M)$, equal to the image of its constituent epimorphism
$n$; i.e., $h(M)=N$. Abusing notation a little further, a function on crosses
is associated with $h$, and we let $h(c)$ denote the cross of $M^{\prime}$ to
which cross $c$ of $M$ is sent by $h$. When the map homomorphism $h$ is given
solely by a sequence of vertex gluings, as represented by riffles, $h$ fixes
each cross (as a map on crosses); it is the involution $\alpha_{1}$ that is
altered. When the map homomorphism $h$ consists solely of a single duplicate
edge gluing, then it sends four crosses to four other crosses, as described in
Definition 16. Further, the isomorphism defining the monomorphism from $h(M)$
into $M^{\prime}$ consists of a bijection between crosses of $h(M)$ and a
subset of crosses of $M^{\prime}$.

Associated with a homomorphism $h:M\to M^{\prime}$, there is a function from
vertices of $M$ to vertices of $M^{\prime}$: the crosses incident with a given
vertex $v$ of $M$ are sent by $h$ to crosses incident with a unique vertex
$v^{\prime}$ in $M^{\prime}$. Likewise, a function is defined by $h:M\to
M^{\prime}$ from edges of $M$ to edges of $M^{\prime}$: the four crosses
incident with an edge $e$ of $M$ are sent by $h$ to four crosses incident with
an edge $e^{\prime}$ in $M^{\prime}$. These two functions on vertices and on
edges define a graph homomorphism between the underlying graphs of $M$ and
$M^{\prime}$.

#### Restriction of a homomorphism.

Lemmas 11 and 12 yield a procedure for converting a sequence of vertex gluings
applied to $M$ into a sequence of vertex gluings applied to a spanning submap
$M\backslash A$ of the same genus and orientability as $M$.

######  Definition 23.

Let $M$ be a map with vertex permutation $\tau$, and $M\backslash A$ a
spanning submap of $M$ of the same signed genus. Let $h=m\circ n$ be a map
homomorphism from $M$ to $M^{\prime}$. The restriction of $h$ to $M\backslash
A$, denoted by $h_{|M\backslash A}:M\backslash A\to M^{\prime}$, is given by
restricting $n$ and $m$ as follows:

Restriction of $n$: first, modify its sequence of vertex gluings to vertex
gluings of $M\backslash A$ by replacing a vertex gluing represented by a
riffle of crosses $a,b$ in $M$ incident with vertices $u,v$ by

  * •

a vertex gluing of $M\backslash A$ represented by a riffle of
$\tau^{i}a,\tau^{j}b$ in $M\backslash A$ (where $i,j\geq 0$ are minimal with
respect to $\tau^{i}a,\tau^{j}b$ being crosses of $M\backslash A$, if such
$i,j$ exist);

  * •

deleting isolated vertex $u$ (if $\tau^{i}a$ is not a cross of $M\backslash A$
for any $i$, but $\tau^{j}b$ is a cross of $M\backslash A$ for some $j$), or
isolated vertex $v$ (if $\tau^{j}b$ is not a cross of $M\backslash A$ for any
$j$, but $\tau^{i}a$ is a cross of $M\backslash A$ for some $i$);

  * •

deleting one of the isolated vertices $u$ and $v$ (if $\tau^{i}a,\tau^{j}b$
are not crosses of $M\backslash A$ for any $i,j$).

Second, modify its sequence of duplicate edge gluings by removing any gluings
of duplicate edges, one or both of which belong to $A$.

Restriction of $m$: we restrict the isomorphism that defines $m$ to the image
of the submap $M\backslash A$ under the restricted epimorphism $n$.

The restriction $h_{|M\backslash A}$ involves gluing the same vertex pairs as
in the sequence of vertex gluings defining the constituent epimorphism of $h$
(what may differ are the faces merged or split by the vertex gluings): the
graph homomorphism corresponding to $h$ from the underlying graph of $M$ to
that of $M^{\prime}$ is restricted to the underlying graph of $M\backslash A$.

Having introduced the restriction to a spanning submap $M\backslash A$, we
next define the restriction of a homomorphism $h:M\to M^{\prime}$ to a submap
$N=(M\backslash A)-U$, where $U$ is a subset of isolated vertices of
$M\backslash A$. To obtain $h_{|N}$ we just perform the restriction
$h_{|M\backslash A}$ with the modification that in the vertex gluing sequence,
when there is a choice between deleting a vertex in $U$ and one outside $U$,
the vertex in $U$ is deleted, and after which any remaining vertices in $U$
are deleted. If $N$ has the same signed genus as $M$, then so does
$M\backslash A$, so we have the following result.

######  Proposition 24.

Let $N$ be a submap of a map $M$ of the same signed genus as $M$, and let
$h:M\to M^{\prime}$ be a homomorphism from $M$ to a map $M^{\prime}$. Then,
the restriction $h_{|N}:N\to M^{\prime}$ is a homomorphism.

In light of the preceeding proposition, one may ask if it is possible to
define a restriction $h_{|N}$ for any submap $N$ even if $N$ is a submap with
a different signed genus as $M$; this is, in general, not possible, as Figure
5 shows; if $N$ is a plane submap, then we are not allowed to follow the
sequence of vertex gluings that $h$ demands. This is the reason for the
condition that $\mathbf{sg}(N)=\mathbf{sg}(M)$.

Figure 5: (a) A map $M$ embedded in the torus, the dotted red and dashed blue
lines indicate gluings of the corresponding vertices, (b) a plane submap $N$
of $M$ in which the vertex gluings of (a) cannot be performed.

#### Composition of homomorphisms.

Let $M,M^{\prime},M^{\prime\prime}$ be maps of the same signed genus, and let
$h:M\to M^{\prime}$ and $h^{\prime}:M^{\prime}\to M^{\prime\prime}$ be
homomorphisms. The image $h(M)$ is a submap of $M^{\prime}$ of the same signed
genus which implies, by Proposition 24, that the restriction
$h^{\prime}_{|h(M)}:h(M)\to M^{\prime\prime}$ is a homomorphism. The
composition of $h^{\prime}_{|h(M)}$ with $h$ defines the composition of $h$
and $h^{\prime}$, which is a homomorphism $h^{\prime}\circ h:M\to
M^{\prime\prime}$.

Decomposing $h=m\circ n$ and $h^{\prime}=m^{\prime}\circ n^{\prime}$ into
their constituent epimorphism and monomorphism, the composition
$h^{\prime}\circ h$ has epimorphism $n^{\prime}_{|h(M)}\circ n$, whose vertex
gluing sequence is the concatenation of the sequence of vertex gluings
defining $n$ and those defining the restriction of $n^{\prime}$ to $h(M)$. The
sequence of duplicate edge gluings is formed from the concatenation of the
sequence of duplicate edge gluings defining $n$ and the inverse image under
$n^{\prime}_{|h(M)}$ of the edges in the sequence of duplicate edge gluings
defining the restriction of $n^{\prime}$ to $h(M)$, where edges in the inverse
image are taken in an arbitrary order.

Since the composition of map homomorphisms is again a map homomorphism, the
existence of a homomorphism between maps defines a transitive relation; as the
identity mapping from $M$ to itself is a homomorphism, this relation defines a
quasi-order on maps. In Section 4.5 a partial order is derived from this
quasi-order by defining the analogue of graph cores for maps.

##  4 Cores

A core of a graph $\Gamma$ [11] is a subgraph $\Delta$ with the property that,
for any graph $\Gamma^{\prime}$, there exists a homomorphism from $\Gamma$ to
$\Gamma^{\prime}$ if and only if there exists a homomorphism from $\Delta$ to
$\Gamma^{\prime}$, and no proper subgraph of $\Delta$ has this property.
Equivalently, $\Delta$ is a core of $\Gamma$ if it is a minimal subgraph of
$\Gamma$ (with respect to containment) for which there exists a graph
homomorphism from $\Gamma$ to $\Delta$. A core of a graph is, up to
isomorphism, unique.

We define cores for maps analogously to how cores are defined for graphs.

######  Definition 25.

A submap $N$ of a map $M$ is a _core_ of $M$ if there is a homomorphism $M\to
N$ but no homomorphism $M\to N^{\prime}$ for any proper submap $N^{\prime}$ of
$N$.

As for graphs, we say that a map is a _core_ when it is its own core. A core
of a map $M$, as a homomorphic image of $M$, has the same signed genus as $M$,
and has no duplicate edges. If a graph is not connected, then its core may
also not be connected (consider, for instance, the disjoint union of $K_{3}$
with the graph obtained from $K_{4}$ by twice subdividing each edge of a
perfect matching, thus having girth four, which is a core as $K_{3}$ is not a
homomorphic image of the subdivided $K_{4}$, and both connected components are
themselves graph cores); the case is similar for maps (a plane embedding of
the previous graph is a map core, as any embedding of a graph core is a map
core). For this reason, we focus on the quasi-ordered set of connected maps.

###  4.1 Basic properties

For a map $M$ with core $N$, a homomorphism from $M$ to $N$ must be surjective
(otherwise $M$ would be mapped to a strict submap of $N$, contradicting that
$N$ is a core). As for graphs, the core of a map is unique.

######  Proposition 26.

If $N$ and $N^{\prime}$ are cores of a map $M$, then $N$ is isomorphic to
$N^{\prime}$.

###### Proof.

We have $\mathbf{sg}(N)=\mathbf{sg}(M)=\mathbf{sg}(N^{\prime})$, and there are
homomorphisms $h:M\to N$ and $h^{\prime}:M\to N^{\prime}$. By Proposition 24,
the restrictions $h_{|N^{\prime}}:N^{\prime}\to N$ and $h^{\prime}_{|N}:N\to
N^{\prime}$ are homomorphisms. In addition, they are surjective since
otherwise the compositions $h_{|N^{\prime}}\circ h^{\prime}$ and
$h^{\prime}_{|N}\circ h$ would be homomorphisms from $M$ to proper submaps of
$N$ and $N^{\prime}$, respectively, contradicting the fact that $N$ and
$N^{\prime}$ are cores. The result now follows from Proposition 21. ∎

In the following proposition we establish that some basic properties of graph
cores [11] have their counterparts for map cores.

######  Proposition 27.

The following statements hold for the core $N$ of a map $M$:

  1. (i)

$N$ is a core (i.e., $N$ is its own core).

  2. (ii)

There is a homomorphism from $M$ to $N$ whose restriction to $N$ is the
identity.

  3. (iii)

$N$ is an induced submap of $M$ after gluing its duplicate edges.

  4. (iv)

Given another map $M^{\prime}$ with core $N^{\prime}$, there is a homomorphism
from $M$ to $M^{\prime}$ if and only if there is a homomorphism from $N$ to
$N^{\prime}$.

###### Proof.

(i) Suppose that there is a homomorphism $h^{\prime}$ from $N$ to a proper
submap $N^{\prime}$ of $N$. We can compose $h^{\prime}$ with a homomorphism
$h:M\to N$ to obtain a homomorphism $h^{\prime}\circ h:M\to N^{\prime}$, which
contradicts the fact that $N$ is a core of $M$. Hence, $N$ is a core.

(ii) Let $h:M\to N$, and consider the restriction $h_{|N}:N\to N$ which, by
Proposition 24, is a homomorphism as $\mathbf{sg}(N)=\mathbf{sg}(M)$. In
addition, it is surjective (since $N$ is a core), and so $h_{|N}$ is an
isomorphism (by Proposition 21 using the identity map as the other
epimorphism). Thus, we can compose $h$ with the inverse of $h_{|N}$ (also an
isomorphism) to obtain a homomorphism from $M$ to $N$, which is the identity
on $N$.

(iii) Duplicate edges in any map can be glued to obtain a proper submap as
homomorphic image and so $N$ cannot contain duplicate edges.

Let $N^{\prime}$ be the submap induced in $M$ by the vertices of $N$ (so $N$
is a spanning submap of $N^{\prime}$). As $\mathbf{sg}(N)=\mathbf{sg}(M)$, by
Lemma 5, we have $\mathbf{sg}(N^{\prime})=\mathbf{sg}(M)$. Let $h:M\to N$ be a
homomorphism that is the identity when restricted to $N$, which we may assume
by (ii). Consider the restriction $h_{|N^{\prime}}:N^{\prime}\to N$, which is
an epimorphism by Proposition 24 and the facts that $N$ is a core of $M$ and
$h$ is the identity on $N$. Definition 20 then establishes that $N$ is
isomorphic to a map obtained from $N^{\prime}$ after a sequence of vertex
gluings followed by a sequence of duplicate edge gluings. Since
$V(N)=V(N^{\prime})$, the sequence of vertex gluings is empty, leaving only a
sequence of duplicate edge gluings. Thus $N$ is the induced submap
$N^{\prime}$ with duplicate edges glued until none remain; see Figure 6 for an
example. Note that the glued edges are duplicated in $N^{\prime}$, but not in
$M$.

(iv) Let $h:M\to N$ be a homomorphism from $M$ to its core $N$. Suppose first
that there is a homomorphism $k:N\to N^{\prime}$. Then the composition $k\circ
h:M\to N^{\prime}$ is a homomorphism, and $N^{\prime}$ is a submap of
$M^{\prime}$ with $\mathbf{sg}(M^{\prime})=\mathbf{sg}(N^{\prime})$. Hence
$k\circ h:M\to M^{\prime}$ is a homomorphism.

Suppose conversely that there is a homomorphism $\ell:M\to M^{\prime}$, and
let $h^{\prime}:M^{\prime}\to N^{\prime}$ be a homomorphism from $M^{\prime}$
to its core $N^{\prime}$. Since $N$ is a submap of $M$ with its same signed
genus, there is the monomorphism $\iota:N\to M$ just seeing $N$ as a submap in
$M$; then the composition $h^{\prime}\circ\ell\circ\iota$ is a homomorphism
between $N$ and $N^{\prime}$ as all the maps have the same signed genus. ∎

Figure 6: A map (left) whose core is a triangle, which is not an induced
submap: the duplicate edge of the submap induced on the three vertices of the
triangle needs to be removed. (Notice that this edge becomes duplicate only
after removing the rightmost vertices.)

The statement of Proposition 27(ii) holds for any submap $N$ of $M$ with the
same signed genus as $M$ (not necessarily a core), as we establish in the
following lemma. This fact will be useful in Section 4.3 as it ensures that
there is an endomorphism of $M$ with image $N$ if and only if there is such an
endomorphism fixing $N$.

######  Lemma 28.

Let $M$ be a map, and let $N$ be a submap of $M$ of the same signed genus. If
there is an epimorphism $n:M\twoheadrightarrow N$, then there is an
epimorphism from $M$ onto $N$ whose restriction to $N$ is the identity.

###### Proof.

If $N$ is the core of $M$ and there is an epimorphism $n:M\twoheadrightarrow
N$, the result follows analogously to Proposition 27(ii). Suppose then that
$N$ is not a core, and let $N_{0}\subset N$ be the core of $N$, and so the
core of $M$ (the epimorphism $n:M\twoheadrightarrow N$ can be composed with an
epimorphism $N\twoheadrightarrow N_{0}$). By Proposition 27(ii), there exists
an epimorphism $n_{0}:M\twoheadrightarrow N_{0}$ whose restriction to $N_{0}$
is the identity. This epimorphism is defined by a sequence of vertex gluings
that gives a map $N_{0}\cup\\{e_{1},\ldots,e_{s}\\}$, where the $e_{i}$’s are
duplicate edges that must be glued to obtain $N_{0}$. Each time that a vertex
gluing is performed, we identify two distinct vertices generating a map that
has one less vertex. In this identification we always try to keep the vertices
in $N_{0}$ or in $N\setminus N_{0}$; note that the two identified vertices
cannot both belong to $V(N_{0})$ as $n_{0}$ is the identity on $N_{0}$. The
sequence of vertex gluings and the duplicate edge gluings can be viewed in the
reverse order: we construct a map $N_{1}$ from $N_{0}$ by not performing the
last vertex gluing of the sequence that removes a vertex from $N\setminus
V(N_{0})$ and not gluing those edges $e_{i}$ that are no longer duplicate with
another edge in $N_{1}$. This creates an epimorphism
$n_{1}:M\twoheadrightarrow N_{1}$ whose restriction to $N_{1}$ is the
identity.

Iterating this procedure, we construct a sequence of maps $N_{0}\subset
N_{1}\subset\ldots\subset N_{k}\subseteq N$, where $N_{i}$ is obtained from
$N_{i-1}$ by not performing the last vertex gluing (in the sequence to obtain
$N_{i-1}$) that removes a vertex from $V(N)\setminus V(N_{i-1})$, and by not
gluing those edges $e_{i}$ that are no longer duplicate in $N_{i}$. We have
$V(N_{k})=V(N)$; then $N$ is obtained from $N_{k}$ by not gluing duplicate
edges of $N$ (which may have been glued to make $N_{k}$ as they had
duplicates). Associated with each $N_{i}$ there is an epimorphism
$n_{i}:M\twoheadrightarrow N_{i}$ whose restriction to $N_{i}$ is the
identity. Thus, the desired epimorphism from $M$ onto $N$ whose restriction to
$N$ is the identity is easily obtained from $n_{k}:M\twoheadrightarrow N_{k}$
when go from $N_{k}$ to $N$. ∎

###  4.2 Separating and contractible cross-circuits

The aim of this section is to translate the topological notions of a simple
(i.e. non-self-intersecting) closed curve, a separating curve and a
contractible curve (or at least contractible curves of a certain type) into
the language of cross permutations defining a map.

In topology, a closed curve in a surface is said to be _contractible_ if it
can be homotopically mapped to a point; equivalently, the curve is contained
within a region of the surface homeomorphic to an open disc. There have been
several translations of this notion into the context of maps, where closed
curves are described by walks, which are defined combinatorially rather than
topologically.

Viewing a map $M$ as an embedding of a graph $\Gamma$ into a surface $\Sigma$,
Mohar and Thomassen [17] define a cycle of $\Gamma$ (a simple circuit,
entering and leaving each vertex at most once) to be contractible in $M$ if
the closed curve that it defines in $\Sigma$ is contractible. One shortcoming
of this definition for our purposes is that it only applies to cycles in
$\Gamma$ and not to closed walks of $\Gamma$ that revisit vertices or edges.
This shortcoming is circumvented by the definition offered by Cabello and
Mohar [2], who define a closed walk of $\Gamma$ to be contractible in $M$ if
the closed curve that it defines in $\Sigma$ can be $\epsilon$-perturbed into
a contractible closed curve in $\Sigma$. Such a perturbation ensures that
there are only finitely many self-intersections, and edges that are traversed
more than once or vertices that are visited more than once by the walk are
represented by disjoint curves or points and are thus distinguished from each
other. Problematic from our perspective is that both these definitions of
contractibility rely on topological properties of curves in $\Sigma$
determined by closed walks of $\Gamma$ rather than properties of the map $M$
as a combinatorial object.

In order to remain within the realm of maps as defined by cross involutions,
we begin by introducing an analogous object to a circuit in a graph; in a
graph a circuit is a closed walk that repeats no edges, in a map it is a
closed walk that repeats no crosses (Definition 29). In this way, we extend
the scope of the term contractibility from the graph cycles of Mohar and
Thomassen to cross-circuits; facial walks are then all contractible, even if
they traverse an edge more than once, corresponding to the defining property
of faces as enclosing topological discs.

######  Definition 29.

Let $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$ be a map with vertex
permutation $\tau$ and face permutation $\phi$. A cross-circuit $\kappa$ of
$M$ is a pair of cycles,

$\kappa=(\;\;c_{0}\;\;\;c_{1}\;\;\;\cdots\;\;\;c_{\ell-1}\;\;)\;(\;\;\alpha_{0}c_{\ell-1}\;\;\;\cdots\;\;\;\alpha_{0}c_{1}\;\;\;\alpha_{0}c_{0}\;\;),$

with the property that the $2\ell$ crosses among
$\\{c_{i}\\}\cup\\{\alpha_{0}c_{i}\\}$ are pairwise distinct and for each $i$
there is a $j$ such that $c_{i}=\tau^{j}\phi c_{i-1}$ (indices $i$ taken
modulo $\ell$).

The two cycles of the cross-circuit $\kappa$ represent its traversal in
opposite directions. Its length is denoted by $\ell(\kappa)$. A facial walk
traversing face $z$ is represented by the cross-circuit $\phi_{z}$.

Recall that a closed walk in a graph is a sequence of edges which joins a
sequence of vertices, starting and ending at the same vertex; for a circuit,
edges are not allowed to be repeated. For orientable maps, we can find a
combinatorial representation using half-edges (considering the set of half-
edges to be the set of crosses in the equivalence classes modulo
$\langle\alpha_{0}\alpha_{2},\phi\rangle$ thus having two half-edges per each
edge in the graph, instead of four crosses). Thus, in a cross-circuit along an
orientable map, we would traverse each half-edge at most once, so each edge at
most twice, once in each direction. If a map is non-orientable, we add an
extra pair of half-edges per edge in the combinatorial representation to make
a total of four crosses; then a cross-circuit only uses each cross from
$\\{c,\alpha_{0}c\\}$ at most once, so each edge is used at most twice.

The choice of cross for a vertex-edge incidence reflects, not only the
direction of travel (we go from $c$ “to $\alpha_{0}c$” and then “to
$\alpha_{1}\alpha_{0}c$”), but also which “side” of the edge the walk is on,
$c$ being on one side and $\alpha_{2}c$ on the other. For instance, which
direction a loop is traversed is determined by which of $c,\alpha_{2}c$ or
$\alpha_{0}c$, $\alpha_{0}\alpha_{2}c$ is chosen to represent the vertex-edge
incidence, and hence the side of the edge as well. A closed walk in a map is
thus given not only by the sequence of vertices and edges, but by the side
along which the edges are traversed – this is determined by how the face
permutation $\phi$ instructs the walk to take a step along an edge, which
explains its role in Definition 29.

A cross-circuit
$(\;\;c_{0}\;\;\;c_{1}\;\;\;\cdots\;\;\;c_{\ell-1}\;\;)\;(\;\;\alpha_{0}c_{\ell-1}\;\;\;\cdots\;\;\;\alpha_{0}c_{1}\;\;\;\alpha_{0}c_{0}\;\;)$
is said to be _non-self-intersecting_ if there are no pair of distinct indices
$(i,j)$ such that the pairs of crosses $\alpha_{0}c_{i},c_{i+1}$ and
$\alpha_{0}c_{j},c_{j+1}$ interlace in a cycle
$(\;\;c\;\;\;\alpha_{1}c\;\;\;\tau
c\;\;\;\tau\alpha_{1}c\cdots\;\;\;\tau^{-1}c\;\;\;\tau^{-1}\alpha_{1}c\;\;)$
consisting of all the crosses incident with a given vertex.

We next present a procedure of cutting a map around a non-self-intersecting
cross-circuit, which leans on two operations that are first defined: edge
splitting and vertex splitting.

######  Definition 30.

Let
$e\equiv(\;\;c\;\;\;\alpha_{0}\alpha_{2}c\;\;)\;(\;\;\alpha_{0}c\;\;\;\alpha_{2}c\;\;)$
be an edge of a map $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$. The map
$M^{\prime}\equiv(C^{\prime},\alpha_{0}^{\prime},\alpha_{1}^{\prime},\alpha_{2}^{\prime})$
obtained from $M$ by splitting edge $e$ into two distinct edges bounding a new
face of degree two is defined as follows:

  * •

$C^{\prime}=C\sqcup\\{\alpha_{2}^{\prime}c$, $\alpha_{2}^{\prime}\alpha_{0}c$,
$\alpha_{2}^{\prime}\alpha_{2}c,\alpha_{2}^{\prime}\alpha_{0}\alpha_{2}c\\}$;

  * •

$\alpha_{0}^{\prime}=\alpha_{0}$ on $C$, and

$\displaystyle\alpha_{0}^{\prime}\,(\alpha_{2}^{\prime}c)$
$\displaystyle=\alpha_{2}^{\prime}\alpha_{0}c\>,$
$\displaystyle\alpha_{0}^{\prime}\,(\alpha_{2}^{\prime}\alpha_{0}c)$
$\displaystyle=\alpha_{2}^{\prime}c\>,$
$\displaystyle\alpha_{0}^{\prime}\,(\alpha_{2}^{\prime}\alpha_{0}\alpha_{2}c)$
$\displaystyle=\alpha_{2}^{\prime}\alpha_{2}c\>,$
$\displaystyle\alpha_{0}^{\prime}\,(\alpha_{2}^{\prime}\alpha_{2}c)$
$\displaystyle=\alpha_{2}^{\prime}\alpha_{0}\alpha_{2}c\>;$

  * •

$\alpha_{2}^{\prime}=\alpha_{2}$ on
$C\setminus\\{c,\alpha_{0}c,\alpha_{2}c,\alpha_{0}\alpha_{2}c\\}$, and

$\displaystyle\alpha_{2}^{\prime}\,(\alpha_{2}^{\prime}c)$
$\displaystyle=c\>,$
$\displaystyle\alpha_{2}^{\prime}\,(\alpha_{2}^{\prime}\alpha_{0}c)$
$\displaystyle=\alpha_{0}c\>,$
$\displaystyle\alpha_{2}^{\prime}\,(\alpha_{2}^{\prime}\alpha_{0}\alpha_{2}c)$
$\displaystyle=\alpha_{0}\alpha_{2}c\>,$
$\displaystyle\alpha_{2}^{\prime}\,(\alpha_{2}^{\prime}\alpha_{2}c)$
$\displaystyle=\alpha_{2}c\>;$

  * •

$\alpha_{1}^{\prime}=\alpha_{1}$ on $C$, and

$\displaystyle\alpha_{1}^{\prime}\,(\alpha_{2}^{\prime}c)$
$\displaystyle=\alpha_{2}^{\prime}\alpha_{2}c\>,$
$\displaystyle\alpha_{1}^{\prime}\,(\alpha_{2}^{\prime}\alpha_{2}c)$
$\displaystyle=\alpha_{2}^{\prime}c\>,$
$\displaystyle\alpha_{1}^{\prime}\,(\alpha_{2}^{\prime}\alpha_{0}c)$
$\displaystyle=\alpha_{2}^{\prime}\alpha_{0}\alpha_{2}c\>,$
$\displaystyle\alpha_{1}^{\prime}\,(\alpha_{2}^{\prime}\alpha_{0}\alpha_{2}c)$
$\displaystyle=\alpha_{2}^{\prime}\alpha_{0}c\>.$

Edge splitting is illustrated in Figure 7(a), where it can be easily seen that
this operation is the inverse to edge gluing (setting $a=\alpha_{2}^{\prime}c$
and $b=\alpha_{2}^{\prime}\,(\alpha_{0}\alpha_{2}c)$ in Definition 16).

######  Definition 31.

Let $a,b$ be a pair of distinct crosses that are coincident with a vertex $v$
of a map $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$. The map $M^{(a\;b)}$
obtained by riffling $a,b$ is the result of _splitting_ the vertex $v$ through
$a,b$.

Vertex splitting is depicted in Figure 7(b). This operation is inverse to
vertex gluing when the pair of crosses $a,b$ satisfy condition (2) of Lemma 7
(see Figure 3). Tutte [19, Ch. X] defines a related operation of vertex
splitting, which follows the operation in Definition 31 by the insertion of a
link joining the two vertices produced by splitting in our sense, in a way
that preserves genus an orientability (exactly how this edge is inserted is
described in the proof of Lemma 7 above). In the proof of Lemma 43 the reader
can find how Tutte’s vertex splitting operation can be recovered using
Definition 31, vertex-gluing, duplicate edge-gluing, and edge addition.

Figure 7: (a) Edge splitting: the new crosses are labeled in blue, (b)
Splitting a vertex of a map $M$ through crosses $a,b$ to make the map
$M^{(a\;b)}$.

Informally, the procedure of cutting around a non-self-intersecting cross-
circuit $\kappa$, which we define next, is performed as follows. While
traversing $\kappa$ we split each edge as we pass through it (in total, we
split each edge as many times as it is traversed). Then, crosses of the split
edges are associated with new faces of degree two (generated by the edge
splitting). The property of non-self-intersecting allows us to merge these new
degree-two faces when splitting vertices: as we proceed, these faces merge
together to make a face of larger even degree until the last step, when the
circuit closes, and the merged face is joined back on itself and the last
vertex-splitting produces two new faces $x$ and $y$. If this last vertex-
splitting disconnects the map, $x$ and $y$ are in different connected
components (in which case the last vertex splitting, as all the previous ones,
is inverse to vertex gluing, and preserves genus and orientability).
Otherwise, the two vertices produced by this last splitting are not incident
with a common face (neither do they belong to different connected components);
one is incident with face $x$ and the other with face $y$.

######  Definition 32.

Let $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$ be a map, and let

$\kappa=(\;\;c_{0}\;\;\;c_{1}\;\;\;\cdots\;\;\;c_{\ell-1}\;\;)\;\;(\;\;\alpha_{0}c_{\ell-1}\;\;\;\cdots\;\;\;\alpha_{0}c_{1}\;\;\;\alpha_{0}c_{0}\;\;)$

be a non-self-intersecting cross-circuit of $M$. The map $M\ltimes\kappa$
obtained from $M$ by _cutting around_ $\kappa$ is the result of: (i) splitting
the edges of $M$ containing $c_{0},c_{1},\ldots,c_{\ell-1}$ in turn, producing
a map
$M^{\prime}\equiv(C^{\prime},\alpha_{0}^{\prime},\alpha_{1}^{\prime},\alpha_{2}^{\prime})$,
(ii) applying the sequence of vertex-splittings in $M^{\prime}$ realized by
riffling crosses $\alpha_{2}^{\prime}\alpha_{0}c_{i}$ and
$\alpha_{1}^{\prime}\alpha_{2}^{\prime}c_{i+1}$ for $i=0,\dots,\ell-1$
(indices modulo $\ell$).

Note that $M\ltimes\kappa$ has the same set of crosses as $M^{\prime}$ in
Definition 32. Figures 8 and 9 illustrate examples of the procedure of cutting
around a non-self-intersecting cross-circuit $\kappa$. The new facial walks
produced by cutting around $\kappa$ are next recorded explicitly.

######  Lemma 33.

Let $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$ be a connected map, and let

$\kappa=(\;\;c_{0}\;\;\;c_{1}\;\;\;\cdots\;\;\;c_{\ell-1}\;\;)\;(\;\;\alpha_{0}c_{\ell-1}\;\;\;\cdots\;\;\;\alpha_{0}c_{1}\;\;\;\alpha_{0}c_{0}\;\;)$

be a non-self-intersecting cross-circuit of $M$. If
$M^{\prime}\equiv(C^{\prime},\alpha_{0}^{\prime},\alpha_{1}^{\prime},\alpha_{2}^{\prime})$
is obtained from $M$ by splitting the edges containing
$c_{0},c_{1},\dots,c_{\ell-1}$ in turn as in Definition 32, then the two
facial walks of $M\ltimes\kappa$ that are not facial walks of $M$ are

$\begin{cases}\kappa_{\ltimes}=(\;\;\alpha_{2}^{\prime}c_{0}\;\;\;\alpha_{2}^{\prime}c_{1}\;\;\;\dots\;\;\;\alpha_{2}^{\prime}c_{\ell-1}\;\;)\;(\;\;\alpha_{0}^{\prime}\alpha_{2}^{\prime}c_{\ell-1}\;\;\;\dots\;\;\;\alpha_{0}^{\prime}\alpha_{2}^{\prime}c_{1}\;\;\;\alpha_{0}^{\prime}\alpha_{2}^{\prime}c_{0}\;\;),\\\
\kappa^{\ltimes}=(\;\;\alpha_{1}^{\prime}\alpha_{2}^{\prime}c_{0}\;\;\;\alpha_{1}^{\prime}\alpha_{2}^{\prime}c_{1}\;\;\;\dots\;\;\;\alpha_{1}^{\prime}\alpha_{2}^{\prime}c_{\ell-1}\;\;)\;(\;\;\alpha_{0}^{\prime}\alpha_{1}^{\prime}\alpha_{2}^{\prime}c_{\ell-1}\;\;\;\dots\;\;\;\alpha_{0}^{\prime}\alpha_{1}^{\prime}\alpha_{2}^{\prime}c_{1}\;\;\;\alpha_{0}^{\prime}\alpha_{1}^{\prime}\alpha_{2}^{\prime}c_{0}\;\;).\end{cases}$

###### Proof.

This follows by recording the effect of splitting edges to form the map
$M^{\prime}$, and splitting vertices visited by $\kappa$. If the vertex being
split is not the last one, the two faces incident with the two riffled crosses
are different; for the last vertex we have crosses coincident with a common
vertex and with a common face. See Figure 7. Vertex splitting after edge
splitting means that we slice between $\alpha_{2}^{\prime}c$ and
$\alpha_{2}^{\prime}\alpha_{2}c$, and between $\alpha_{2}^{\prime}\alpha_{0}c$
and $\alpha_{2}^{\prime}\alpha_{0}\alpha_{2}c$ in Figure 7(a) all along the
edges of $\kappa$. ∎

The effect of vertex splitting on the signed genus in the cases that arise
when we cut around a non-self-intersecting cross-circuit is presented in the
following lemma.

######  Lemma 34.

Let $M\equiv(C,\alpha_{0},\alpha_{1},\alpha_{2})$ be a connected map, and let
$a,b$ be crosses of $M$ that are coincident with a vertex $w$. After vertex
splitting $w$ through $a,b$ to make the map $M^{(\,a\>b\,)}$:

  1. (i)

If $a,b$ are incident with distinct faces, then
$\mathbf{k}(M^{(\,a\>b\,)})=\mathbf{k}(M)$ and
$\mathbf{sg}(M^{(\,a\>b\,)})=\mathbf{sg}(M)$.

  2. (ii)

If $a,b$ are coincident with a common face and
$\mathbf{k}(M^{(\,a\>b\,)})>\mathbf{k}(M)$, then
$\mathbf{sg}(M^{(\,a\>b\,)})=\mathbf{sg}(M)$.

  3. (iii)

If $a,b$ are coincident with a common face and
$\mathbf{k}(M^{(\,a\>b\,)})=\mathbf{k}(M)$, then
$\mathbf{sg}(M^{(\,a\>b\,)})\neq\mathbf{sg}(M)$.

###### Proof.

(i) In this case, crosses $a,b$ are in $M^{(\,a\>b\,)}$ incident with
different vertices and coincident with a common face, so, by Lemma 7 and since
$[M^{(\,a\>b\,)}]^{(\,a\>b\,)}=M$, we have
$\mathbf{sg}(M^{(\,a\>b\,)})=\mathbf{sg}(M)$. That
$\mathbf{k}(M^{(\,a\>b\,)})=\mathbf{k}(M)$ follows from the fact that the
Euler characteristic and Euler genus are unchanged.

(ii) The assumption on the number of connected components implies that
splitting $w$ into $u$ and $v$ disconnects the component of $M^{(\,a\>b\,)}$
containing $u$ from the one containing $v$. Therefore, crosses $a,b$ are in
$M^{(\,a\>b\,)}$ incident with vertices and faces in different connected
components. By Lemma 7, the result follows.

(iii) From $\mathbf{v}(M^{(\,a\>b\,)})=\mathbf{v}(M)+1$,
$\mathbf{e}(M^{(\,a\>b\,)})=\mathbf{e}(M)$ and
$\mathbf{f}(M^{(\,a\>b\,)})=\mathbf{f}(M)+1$, it follows that
$\boldsymbol{\chi}(M^{(\,a\>b\,)})=\boldsymbol{\chi}(M)+2$. The latter,
together with the assumption $\mathbf{k}(M^{(\,a\>b\,)})=\mathbf{k}(M)$,
implies that $\mathbf{eg}(M^{(\,a\>b\,)})=\mathbf{eg}(M)+2$. Hence,

$\mbox{if}\hskip
19.91684pt\begin{cases}\mathbf{o}(M^{(\,a\>b\,)})=\mathbf{o}(M)=2\\\
\mathbf{o}(M^{(\,a\>b\,)})=\mathbf{o}(M)=1\\\
\mathbf{o}(M^{(\,a\>b\,)})=2,\mathbf{o}(M)=1\\\
\mathbf{o}(M^{(\,a\>b\,)})=1,\mathbf{o}(M)=2\end{cases}\hskip
19.91684pt\mbox{then}\hskip
19.91684pt\begin{cases}\mathbf{sg}(M^{(\,a\>b\,)})=\mathbf{sg}(M)+1\\\
\mathbf{sg}(M^{(\,a\>b\,)})=\mathbf{sg}(M)-2\\\
\mathbf{sg}(M^{(\,a\>b\,)})=1-\frac{\mathbf{sg}(M)}{2}\\\
\mathbf{sg}(M^{(\,a\>b\,)})=-2\mathbf{sg}(M)-2\qquad\qed\end{cases}$

The map $M\ltimes\kappa$ is produced from $M$ by first splitting (or
duplicating) the edges of $\kappa$, which does not change the signed genus of
$M$, and then by a sequence of vertex-splittings. When $\kappa$ is a non-self-
intersecting cross-circuit of $M$, by Lemma 34(i) splitting its vertices
visited in turn does not change the number of connected components until
possibly when splitting the last vertex. In the notation of Definition 32,
this last vertex-splitting is realized by riffling the crosses
$\alpha_{2}^{\prime}\alpha_{0}c_{\ell}$ and $\alpha_{2}^{\prime}c_{0}$, which
are coincident with a common vertex and with a common face, and so
$\textbf{k}(M)\leq\textbf{k}(M\ltimes\kappa)\leq\textbf{k}(M)+1.$ When
$\textbf{k}(M\ltimes\kappa)=\textbf{k}(M)$, the non-self-intersecting cross-
circuit $\kappa$ is said to be _non-separating_ , and it is _separating_ if
$\textbf{k}(M\ltimes\kappa)=\textbf{k}(M)+1$. Lemma 34(iii) and Lemma 34(ii)
give the effect on the signed genus for these two cases.

When $\kappa$ is a separating cross-circuit of a connected map $M$, the map
$M\ltimes\kappa$ is the disjoint union of two maps:

  * •

a connected map $M_{\kappa}$ containing the crosses of $\kappa$ and the facial
walk $\kappa_{\ltimes}$, and

  * •

a connected map $M^{\kappa}$ containing the crosses of the facial walk
$\kappa^{\ltimes}$.

The facial walks $\kappa_{\ltimes}$ and $\kappa^{\ltimes}$ are both described
in Lemma 33; see also Figures 8 and 9. We say that $\kappa$ is _contractible_
if $M_{\kappa}$ or $M^{\kappa}$ is a plane map. For non-connected maps, a
cross-circuit is said to be contractible if it has this property in its own
connected component. This notion of contractibility includes, as a special
case, the contractible cycles as defined by Mohar and Thomassen [17], and is
consistent with the definition given by Cabello and Mohar [2] when restricting
the latter to those curves that can be $\epsilon$-perturbed so as not to be
self-intersecting. (Our term “contractible” assumes that the cross-circuit is
separating and therefore non-self-intersecting.)

######  Definition 35.

A contractible cross-circuit $\kappa$ of a connected map $M$ is said to be
_prefacial_ if $M_{\kappa}$ is plane and the facial walk $\kappa_{\ltimes}$
traverses a cycle in the underlying graph of $M_{\kappa}$.

Asking a cross-circuit $\kappa$ to be prefacial adds to the contractibility
constraint that it is contractible in a certain direction ($M_{\kappa}$ is
plane), and the constraint on the facial walk $\kappa_{\ltimes}$ adds an
irreducibility condition. Figure 8 illustrates a contractible cross-circuit
that is not prefacial because its direction of contraction is not toward the
plane part. An example of a contractible cross-circuit $\kappa$ with
$M_{\kappa}$ plane and not prefacial is given by traversing two plane loops on
a vertex along the half-edges “inside” the loops. (Or take $\kappa$ given by
$(\;a\;\;\phi a\;\;b\;\;\phi b\;\;\phi^{2}b\;)$ in the right-hand map in
Figure 3(a).) Figure 9 illustrates a prefacial cross-circuit.

Figure 8: A cross-circuit $\kappa$ in a map $M$ (embedded in the torus) given
by $(\;c_{0}\;\;c_{1}\;\;c_{2}\;\;c_{3}\;)$. Splitting the edges containing
crosses of $\kappa$ (edges in dark grey) gives the map $M^{\prime}$ (edges in
light grey come from some edge splitting). The map $M\ltimes\kappa$ is then
obtained by a sequence of vertex-splittings in $M^{\prime}$: it is the
disjoint union of $M_{\kappa}$ and $M^{\kappa}$. The cross-circuit $\kappa$ is
contractible ($M^{\kappa}$ is plane) and not prefacial ($M_{\kappa}$ is not
plane).  Figure 9: A cross-circuit $\kappa$ in a map $M$ (embedded in the
torus) given by
$(\;c_{0}\;\;c_{1}\;\;c_{2}\;\;c_{3}\;\;c_{4}\;\;c_{5}\;\;c_{6}\;\;c_{7}\;)$.
The map $M^{\prime}$ is obtained by splitting the edges containing crosses of
$\kappa$ (edges in dark grey); each edge is split twice as it contains two
crosses in the cycle defining $\kappa$ (edges in light grey come from some
edge splitting). The map $M\ltimes\kappa$ is then obtained by a sequence of
vertex-splittings in $M^{\prime}$: it is the disjoint union of $M_{\kappa}$
and $M^{\kappa}$. The cross-circuit $\kappa$ is prefacial.

###  4.3 Cross-circuits and homomorphisms

In this section, we present technical tools on the interaction between map
homomorphisms and different types of cross-circuits; this leads to the
characterization of map cores (Theorem 41). We begin by showing that there is
a correspondence between prefacial cross-circuits of a connected map and
facial walks of any connected submap of the same signed genus. Prefacial