ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P2.06 / 271–286
https://doi.org/10.26493/1855-3974.2053.c7b
(Also available at http://amc-journal.eu)
A-trails of embedded graphs and twisted duals*
Qi Yan †
School of Mathematics, China University of Mining and Technology,
Xuzhou 221116, P. R. China, and
School of Mathematical Sciences, Xiamen University, Xiamen 361005, P. R. China
Xian’an Jin ‡
School of Mathematical Sciences, Xiamen University, Xiamen 361005, P. R. China
Received 18 July 2019, accepted 15 August 2021, published online 27 May 2022
Abstract
Kotzig showed that every connected 4-regular plane graph has an A-trail—an Eulerian
circuit that turns either left or right at each vertex. However, this statement is not true for
Eulerian plane graphs and determining if an Eulerian plane graph has an A-trail is NP-
hard. The aim of this paper is to give a characterization of Eulerian embedded graphs
having an A-trail. Andersen et al. showed the existence of orthogonal pairs of A-trails
in checkerboard colourable 4-regular graphs embedded on the plane, torus and projective
plane. A problem posed in their paper is to characterize Eulerian embedded graphs (not
necessarily checkerboard colourable) which contain two orthogonal A-trails. In this article,
we solve this problem in terms of twisted duals. Several related results are also obtained.
Keywords: Embedded graphs, twisted duals, Eulerian, A-trails, checkerboard colourable.
Math. Subj. Class. (2020): 05C10, 05C45, 05C62
1 Introduction
A cellularly embedded graph is a graph G embedded in a surface Σ such that every con-
nected component of Σ − G is a 2-cell, called a face. We use the term embedded graph
loosely to mean any of three equivalent representations of graphs in surfaces: cellularly em-
bedded graphs, ribbon graphs and arrow presentations. We shall move from one to another
*We thank Graham Farr, Yichao Chen and the referees sincerely for their valuable comments.
†Corresponding author. This work is supported by NSFC (No. 12101600) and the Fundamental Research
Funds for the Central Universities (No. 2021QN1037)
‡This work is supported by NSFC (No. 12171402) and the Fundamental Research Funds for the Central Uni-
versities (No. 20720190062).
E-mail addresses: qiyan@cumt.edu.cn (Qi Yan), xajin@xmu.edu.cn (Xian’an Jin)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
272 Ars Math. Contemp. 22 (2022) #P2.06 / 271–286
freely and refer the reader to [5, 6, 10] for details. A quasi-tree is an embedded graph with
exactly one boundary component (or face). A bouquet is an embedded graph with exactly
one vertex. They are geometric duals to each other. A quasi-tree bouquet is a bouquet that
is also a quasi-tree.
In this article, all graphs will be finite, connected, but not necessarily simple. A graph
is said to be Eulerian if the degree of each of its vertices is even. A graph is bipartite if its
vertex set can be partitioned into two nonempty subsets X and Y so that every edge has
one end in X and one end in Y . We denote a bipartite graph G with bipartition (X,Y )
by G[X,Y ]. Note that bipartite graphs might have multiple edges but not loops. A star
is a bipartite graph G[X,Y ] with |X| = 1 or |Y | = 1. A parallel graph, also known
as a generalized theta graph especially for 3 or more edges, is a special star G[X,Y ] with
|X| = 1 and |Y | = 1. A walk in a graph between vertices v0 and vk is a sequence of
vertices and edges (v0, e1, v1, e2, · · · , ek, vk), where vi−1 and vi are the endvertices of the
edge ei. A trail is a walk with no repeated edge and circuit is a trail with v0 = vk. An
A-trail [7] in an Eulerian embedded graph G is an eulerian circuit such that every two
consecutive edges in the circuit are adjacent in the rotation of the common vertex. A Petrie
walk in an embedded graph G is such a walk that when traveling along it, we alternatingly
turn to the left edge and to the right edge of the current edge in the cyclic rotation around
the common vertex. It is obvious that an Eulerian Petrie walk is a special kind of A-trails.
Kotzig [7] showed that every 4-regular plane graph has an A-trail, and sufficient con-
ditions were discovered for the existence of A-trails in 2-connected plane graphs in [2].
The existence of A-trails has been studied almost exclusively in the case of graphs em-
bedded in the plane, the projective plane and the torus. In this paper, we shall charac-
terize general Eulerian embedded graphs having an A-trail in terms of twisted duals. Let
G = (V (G), E(G)) be an embedded graph. We denote by G∗ and G× the geometric
dual and Petrial [14] of G, respectively. Let A ⊆ E(G). We denote by Gδ(A) and Gτ(A)
the partial dual [4] and partial Petrial of G with respect to A, respectively. Particularly, if
A = E(G), then Gδ(E(G)) = G∗ and Gτ(E(G)) = G×. Partial duality and partial Petriality
are further combined together to form twisted duality [1, 5]. The twisted duality has the
scope to develop the understanding of a wide variety of graph theoretical problems. We
refer the reader to [5, 6] for the details. Petrie walks have some very interesting properties,
see [8, 12]. They also play an important role in the design of CMOS VLSI circuits, where
it is convenient if the graph representing a circuit has an Eulerian Petrie walk. Žitnik [13]
gave a characterization of 4-regular plane graphs with Eulerian Petrie walks. Since Eule-
rian Petrie walks are a special kind of A-trails, we also give a characterization of Eulerian
embedded graphs having an Eulerian Petrie walk. We first obtain the following theorem.
Theorem 1.1. Let G be an Eulerian embedded graph. Then G has an A-trail if and only if
there exists B ⊆ E(G) such that the underlying graph of (Gτ(B))∗ is a star. In particular,
G has an Eulerian Petrie walk if and only if the underlying graph of (G×)∗ is a star.
Andersen, Bouchet and Jackson [3] characterized the 4-regular plane graphs which
contain two orthogonal A-trails, that is to say two A-trails for which no subtrail of length 2
appears in both A-trails. They also discussed the corresponding problem for checkerboard
colourable graphs embedded in the projective plane and the torus. And they posed the
following problem.
Problem 1.2 ([3]). We do not have any characterization of 4-regular graphs in the projec-
tive plane and the torus having two orthogonal A-trails which we know to be valid also for
Q. Yan and X. Jin: A-trails of embedded graphs and twisted duals 273
graphs with no 2-face colouring.
In this paper, we give a general definition of two orthogonal A-trails in Eulerian em-
bedded graphs. We say that two A-trails are orthogonal if these two trails have different
transitions at each vertex with degree greater than 2. We consider the above problem for
general Eulerian embedded graphs which may have high genus and are not necessarily
checkerboard colourable and characterize the Eulerian embedded graphs which have two
orthogonal A-trails or Eulerian Petrie walks in terms of twisted duals as follows.
Theorem 1.3. Let G be an embedded graph. Then G has two orthogonal A-trails if and
only if there exists B ⊆ E(G) such that the underlying graph of (Gτ(B))∗ is a parallel
graph. In particular, G has two orthogonal Eulerian Petrie walks if and only if the under-
lying graph of (G×)∗ is a parallel graph.
In the case of 4-regular embedded graphs, we have the following theorem.
Theorem 1.4. Let H be a 4-regular embedded graph. Then H has two orthogonal A-trails
if and only if there exists D ⊆ E(H) such that Hτ(D) is a medial graph of a quasi-tree
bouquet. Particularly, H has two orthogonal Eulerian Petrie walks if and only if H× is a
medial graph of a quasi-tree bouquet.
2 Preliminaries
In this section we introduce the notions and the tools, which we will need in further Sec-
tions 3 and 4. We use standard notations V (G), E(G) and F (G) to denote the sets of ver-
tices, edges, and faces, respectively, of a cellularly embedded graph G and
v(G) = |V (G)|, e(G) = |E(G)| and f(G) = |F (G)|, respectively. We denote by d(v) the
degree of a vertex v in G, i.e. the number of half-edges incident with v. We give a brief
review of ribbon graphs referring the reader to [5, 6] for further details.
Definition 2.1 ([6]). A ribbon graph G = (V (G), E(G)) is a (possibly non-orientable)
surface with boundary, represented as the union of two sets of topological discs, a set
V (G) of vertices, and a set E(G) of edges such that
1. the vertices and edges intersect in disjoint line segments, we call them common line
segments as in [9];
2. each such common line segment lies on the boundary of precisely one vertex and
precisely one edge;
3. every edge contains exactly two such common line segments.
Let G be a ribbon graph, v ∈ V (G) and e ∈ E(G). By deleting the common line
segments from the boundary of v, we obtain d(v) disjoint line segments, called vertex
line segments. By deleting common line segments from the boundary of e, we obtain two
disjoint line segments, called edge line segments. See Figure 1 for an example of these
concepts. We think of each edge line segment having two half-edge line segments. It is
obvious that every edge disc contains four half-edge line segments which correspond to
the four flags incident on that edge. For any vertex line segment, there are exactly two
half-edge line segments incident with it as shown in Figure 2.
274 Ars Math. Contemp. 22 (2022) #P2.06 / 271–286
Figure 1: Vertex line segments (yellow), common line segments (red) and edge line seg-
ments (blue).
Let G be a ribbon graph and A ⊆ E(G). Then the partial Petrial, Gτ(A), of G with
respect to A is the ribbon graph obtained from G by adding a half-twist to each of the edges
in A. Let Orb(τ)(G) = {Gτ(A)|A ⊆ E(G)} denote the set of all partial Petrials of G. Let
H be an arrow presentation and B ⊆ E(H). Then the partial dual, Hδ(B), of H with
respect to B is the arrow presentation obtained as follows. For each e ∈ B, suppose α and
β are the two arrows labelled e in the arrow presentation of H . Draw a line segment with
an arrow on it directed from the head of α to the tail of β, and a line segment with an arrow
on it directed from the head of β to the tail of α. Label both of these arrows e and delete α
and β and the arcs containing them. This process is illustrated locally at a pair of arrows in
Figure 3. Let Orb(δ)(H) = {Hδ(B)|B ⊆ E(H)} denote the set of all partial duals of H .
Figure 2: Four half-edge line segments of e, one of the vertex line segments of v and its
incident two half-edge line segments.
Let B =< δ, τ |δ2, τ2, (δτ)3 >.
Definition 2.2 ([5]). Let G be a ribbon graph. The ribbon graph H is called a twisted dual
(briefly, twual) of G if it can written in the form
H = GΠ
6
i=1ξi(Ai),
where the Ai’s partition E(G) and the ξi’s are the six elements of B.
Q. Yan and X. Jin: A-trails of embedded graphs and twisted duals 275
Figure 3: Taking the partial dual of an edge in an arrow presentation.
If G is cellularly embedded in Σ, we construct its medial graph Gm in the embed-
ded surface by placing a vertex on each of its edges, and for each face f with boundary
e1, e2, · · · , ed(f), drawing d(f) edges {e1, e2}, · · · , {ed(f), e1} inside the face f along the
boundary of f . It is obvious that Gm is also cellularly embedded in Σ. In particular, the
medial graph of an isolated vertex is a free loop. G is checkerboard colourable if the faces
of G can be properly 2-coloured. A checkerboard colouring of G is a particular proper
2-colouring of the faces of G. Throughout we will use red and blue to refer to the two
colours used in a checkerboard colouring. It is obvious that there is a correspondence be-
tween checkerboard colouring and face boundary colouring, so we shall move from one
to another freely. Note that in a checkerboard coloured 4-regular embedded graph G, the
redface graph GR of G is the embedded graph constructed by placing one vertex in each
red face and adding an edge between two of these vertices whenever the corresponding
faces meet at a vertex of G. The blueface graph GB is constructed analogously by placing
vertices in the blue faces.
A Petrie walk in an embedded graph G is such a walk that when traveling along it, we
alternatingly turn to the left edge and to the right edge of the current edge in the cyclic rota-
tion around the common vertex. We shall only consider closed Petrie walks, for which this
condition holds also for the last and the first edge of the walk. Petrie walks are sometimes
also called left-right paths. An example of a Petrie walk is shown in Figure 4, where the
dotted curve indicates the order of edges in the walk. Note that the boundary components
of faces of the Petrie dual are exactly Petrie walks of the original embedding of G as shown
in Figure 5.
Figure 4: The curve representing a Petrie walk.
Let v be a vertex of G. A transition at v is a partition of the half-edges incident to v into
276 Ars Math. Contemp. 22 (2022) #P2.06 / 271–286
Figure 5: A Petrie walk corresponding to a face of the Petrie dual of the original embedded
graph.
pairs. A transition T at v is smooth if T only pairs half-edges adjacent in the cyclic order at
v given by the embedding of G. A transition system of G is a choice of a transition at every
vertex of G. A smooth transition system is a transition system such that every transition
is smooth. It is obvious that we can induce a circuit decomposition of G by a transition
system T . Similarly, any circuit decomposition C of G recovers a transition system of G
by pairing half-edges traversed consecutively in a circuit of C. A circuit decomposition of
G is smooth if it induces a smooth transition system. In particular, an Eulerian circuit that
induces a smooth transition system is called an A-trail [11]. Note that there are precisely
two disjoint smooth transitions for any vertex v of G with d(v) ≥ 4 and two edges are
consecutive if this is indicated by a curve as shown in Figure 6. We say that two A-trails
Figure 6: Performing exactly two smooth transitions locally at a vertex.
(or smooth transition systems) of an Eulerian embedded graph G are orthogonal if the two
trails (or smooth transition systems) have different smooth transitions at each vertex v of G
with d(v) ≥ 4.
Most of the representations of embedded graphs are ribbon graphs in this paper, so we
introduce the relation between smooth transition systems and ribbon graphs. Let G be an
Eulerian ribbon graph. For every v ∈ V (G), we assign the colours red and blue to all
half-edge line segments and vertex line segments of v such that the colours of vertex line
segments are alternating red and blue in the vertex boundary of v and every vertex line
segment and two half-edge line segments incident with it assign the same colour. We call
this a checkerboard colouring of half-edge and vertex line segments of G (see Figure 7 for
Q. Yan and X. Jin: A-trails of embedded graphs and twisted duals 277
example). If G is checkerboard coloured of half-edge and vertex line segments, then for any
edge disc, there are exactly two cases as shown in Figure 8. The edge is called consistent
if two half-edge line segments of one of edge line segments have the same colour, and is
called inconsistent otherwise. Let T be a smooth transition system of G. It is obvious that
T induces a checkerboard colouring of half-edge and vertex line segments for any vertex of
G as shown in Figure 9. We call this a canonical checkerboard colouring of half-edge and
vertex line segments by T . An example of a canonical checkerboard colouring of half-edge
and vertex line segments by the smooth transition system is given in Figure 10.
Figure 7: A checkerboard colouring of half-edge and vertex line segments at a vertex.
Figure 8: (a) consistent edge (b) inconsistent edge.
3 Main results and proofs
Now we give some characterizations of Eulerian embedded graphs having an A-trail or
Eulerian Petrie walk. Kotzig [7] showed that every 4-regular plane graph has an A-trail.
We note that this result can be extended to any 4-regular embedded graph.
Lemma 3.1. Any 4-regular embedded graph always has an A-trail.
Proof. Let T be any smooth transition system of a 4-regular embedded graph H . Note
that each smooth transition system corresponds to a specific family of edge-disjoint cycles
278 Ars Math. Contemp. 22 (2022) #P2.06 / 271–286
Figure 9: The relation between smooth transition and checkerboard colouring of half-edge
and vertex line segments at a vertex.
Figure 10: An example of a canonical checkerboard colouring of half-edge and vertex line
segments by the smooth transition system.
Q. Yan and X. Jin: A-trails of embedded graphs and twisted duals 279
in H . The number of edge-disjoint cycles in H generated by T will be denoted by c(T ).
If c(T ) = 1, then this completes the proof. Otherwise, there exists v ∈ V (H) such
that four half-edges 1, 2, 3, 4 incident with v are not in the same cycle. Assume that the
transition at v is (1, 2), (3, 4). Then we change the smooth transition of v from (1, 2), (3, 4)
to (1, 4), (2, 3). Hence, half-edges 1, 2, 3, 4 are in the same edge-disjoint cycle as shown
in Figure 11. Repeating the above process, we obtain a smooth transition system which
corresponds to an A-trail.
Figure 11: Proof of Lemma 3.1.
Lemma 3.1 can not be further generalized to any Eulerian embedded graph and an
example is given in Figure 12. Note that taking partial petrial does not affect cyclic order
Figure 12: An Eulerian embedded graph which does not have an A-trail.
of half-edges at vertices, we have the following lemma.
Lemma 3.2. Let G be an Eulerian embedded graph. Then
(1) G has an A-trail if and only if every partial Petrial of G has an A-trail.
(2) G has two orthogonal A-trails if and only if every partial Petrial of G has two or-
thogonal A-trails.
Theorem 1.1. Let G be an Eulerian embedded graph. Then G has an A-trail if and only if
there exists B ⊆ E(G) such that the underlying graph of (Gτ(B))∗ is a star. In particular,
G has an Eulerian Petrie walk if and only if the underlying graph of (G×)∗ is a star.
280 Ars Math. Contemp. 22 (2022) #P2.06 / 271–286
Proof. (⇒) Let G be a ribbon graph. If G has an A-trail, then there exists a smooth
transition system T of G corresponding to the A-trail. We get a canonical checkerboard
colouring of half-edge and vertex line segments according to T . Suppose that B is the set
of its inconsistent edges. If the A-trail is an Eulerian Petrie walk, then B = E(G). Thus
Gτ(B) obtains a face boundary colouring. It induces a checkerboard colouring with only
one red face. Then (Gτ(B))∗ is bipartite with |X| = 1 or |Y | = 1, hence the underlying
graph of (Gτ(B))∗ is a star.
(⇐) Since the underlying graph of (Gτ(B))∗[X,Y ] is a star, we assume that X = {v}.
Note that v corresponds to a face of Gτ(B). We assign the colour red to this face and colour
blue to other faces of Gτ(B). This is a checkerboard colouring of Gτ(B). Suppose that it
is a canonical checkerboard colouring of half-edge and vertex line segments of Gτ(B). Let
T be the corresponding smooth transition system. It follows that T induces an A-trail of
Gτ(B). Thus, G has an A-trail by Lemma 3.2. If B = E(G), then this is a checkerboard
colouring of G×. Hence, the boundary of the redface of G× is an Eulerian Petrie walk of
G.
Remark 3.3. According to Theorem 1.1, suppose that G is an embedded graph whose
underlying graph is a star. If H ∈ Orb(τ)(G∗), then H has an A-trail. Particularly, if
H = (G∗)×, then H has an Eulerian Petrie walk.
Corollary 3.4. Let H be a 4-regular embedded graph. Then H has an Eulerian Petrie
walk if and only if H× is a medial graph of a bouquet.
Proof. By a similar argument as in the proof of Theorem 1.1, H× can obtain a checker-
board colouring with only one red face. Hence, the number of vertices of the redface graph
(H×)R is exactly one, that is a bouquet. Therefore, H× is a medial graph of a bouquet.
Conversely, let G be a bouquet and H× is the medial graph of G. We give Gm a checker-
board colouring where the red faces contain the vertices of G. Then the number of red
faces is exactly one. Hence, (Gm)∗ is a star. Thus, (Gm)× has an Eulerian Petrie walk by
Remark 3.3. Since Gm = H×, we can see that H has an Eulerian Petrie walk.
Theorem 1.3. Let G be an embedded graph. Then G has two orthogonal A-trails if and
only if there exists B ⊆ E(G) such that the underlying graph of (Gτ(B))∗ is a parallel
graph. In particular, G has two orthogonal Eulerian Petrie walks if and only if the under-
lying graph of (G×)∗ is a parallel graph.
Proof. (⇒) Assume that T and T ′ are two orthogonal smooth transition systems recov-
ering from the two orthogonal A-trails of a ribbon graph G. Then we get a canonical
checkerboard colouring of half-edge and vertex line segments according to T . Suppose
that B is the set of its inconsistent edges. If the A-trail is an Eulerian Petrie walk, then
B = E(G). By the same argument as in the proof of Theorem 1.1, there is a face boundary
colouring of Gτ(B) such that the number of colour red face boundaries is exactly one. Note
that T ′ corresponds to the blue face boundaries of Gτ(B). It follows that the number of
colour blue face boundary is also exactly one. Hence, the vertex set of (Gτ(B))∗ can be
partitioned into two subsets X and Y with |X| = |Y | = 1. Thus, the underlying graph of
(Gτ(B))∗ is a parallel graph.
(⇐) Since the underlying graph of (Gτ(B))∗ is a parallel graph with vertices v and w.
Note that the number of face boundaries of Gτ(B) are two, which correspond to v and w,
respectively. We give one colour red and another colour blue. Hence, this is a checkerboard
Q. Yan and X. Jin: A-trails of embedded graphs and twisted duals 281
colouring of Gτ(B). Let T and T ′ be the corresponding two orthogonal smooth transition
systems to the red face boundary and the blue face boundary, respectively. It is obvious that
T and T ′ induce two orthogonal A-trails of Gτ(B). Thus, G has two orthogonal A-trails
by Lemma 3.2. If B = E(G), then this is a checkerboard colouring of G×. Note that
the redface and blueface of G× are both Eulerian Petrie walks of G. Hence, G has two
orthogonal Eulerian Petrie walks.
Remark 3.5. According to Theorem 1.3, suppose that G is an embedded graph whose
underlying graph is a parallel graph. If H ∈ Orb(τ)(G∗), then H has two orthogonal
A-trails. In particular, if H = (G∗)×, then H has two orthogonal Eulerian Petrie walks.
Theorem 1.4. Let H be a 4-regular embedded graph. Then H has two orthogonal A-trails
if and only if there exists D ⊆ E(H) such that Hτ(D) is a medial graph of a quasi-tree
bouquet. Particularly, H has two orthogonal Eulerian Petrie walks if and only if H× is a
medial graph of a quasi-tree bouquet.
Proof. (⇒) By the same argument as in the proof of Theorem 1.3, there exists D ⊆ E(H)
such that there is a checkerboard colouring of Hτ(D) which the number of colour red
face and blue face are both exactly one, that is, the number of vertices of (Hτ(D))R and
(Hτ(D))B are both exactly one. Note the number of face of (Hτ(D))R is also one, since
(Hτ(D))R and (Hτ(D))B are geometric duals. Therefore, (Hτ(D))R is a quasi-tree bou-
quet. Hence, Hτ(D) is a medial graph of a quasi-tree bouquet.
(⇐) Let G be a quasi-tree bouquet and Hτ(D) be the medial graph of G. Since G and
Gm embedded in the same surface, we have v(G) − e(G) + f(G) = v(Gm) − e(Gm) +
f(Gm) by Euler characteristic. Note that v(Gm) = e(G), e(Gm) = 2v(Gm) = 2e(G).
Hence, f(Gm) = v(G)+f(G) = 2. Thus, (Gm)∗ is a parallel graph since Gm is checker-
board colourable and f(Gm) = 2. Then Gm has two orthogonal A-trails by Theorem 1.3,
that is, Hτ(D) has two orthogonal A-trails. Hence, H has two orthogonal A-trails by
Lemma 3.2. If D = E(H), then (H×)∗ is a parallel graph. It follows that H has two
orthogonal Eulerian Petrie walks by Remark 3.5.
Remark 3.6. According to Theorem 1.4, suppose that G is a quasi-tree bouquet. If H ∈
Orb(τ)(Gm), then H has two orthogonal A-trails. In particular, if H = (Gm)×, then H
has two orthogonal Eulerian Petrie walks.
Lemma 3.7. Let G be an embedded graph. Then E(G) can be partitioned into two edge
disjoint spanning quasi-trees if and only if G is the partial dual of a quasi-tree bouquet.
Proof. Suppose A and Ac are the edge sets of two spanning quasi-trees which partition
E(G), then Gδ(A) is a bouquet since the vertex boundaries of Gδ(A) correspond to the face
boundaries of (V (G), A) which is a spanning quasi-tree. Thus, Gδ(A
c) is also a bouquet by
the similar discussion. Note that Gδ(A) = (Gδ(A
c))∗. Hence, Gδ(A) is a quasi-tree bouquet,
that is, G is the partial dual of a quasi-tree bouquet. Conversely, there exists A ⊆ E(G)
such that Gδ(A) is a quasi-tree bouquet. Then Gδ(A
c) is also a bouquet. It follows that
(V (G), A) and (V (G), Ac) are both spanning quasi-trees, that is, E(G) can be partitioned
into two edge disjoint spanning quasi-trees.
Lemma 3.8 ([5]). Let G be an embedded graph. Then
Orb(δ)(G) = {H|Gm and Hm are partial Petrials}.
282 Ars Math. Contemp. 22 (2022) #P2.06 / 271–286
Corollary 3.9. Let H be a checkerboard coloured 4-regular embedded graph. Then H has
two orthogonal A-trails if and only if the edges of the redface graph HR can be partitioned
into two edge disjoint spanning quasi-trees.
Proof. E(HR) can be partitioned into two edge disjoint spanning quasi-trees if and only if
HR is the partial dual of a quasi-tree bouquet by Lemma 3.7, that is, there exists D ⊆ E(H)
such that Hτ(D) is a medial graph of a quasi-tree bouquet by Lemma 3.8, if and only if H
has two orthogonal A-trails by Theorem 1.4.
Corollary 3.10. Let H be a checkerboard coloured 4-regular orientable embedded graph
which has two orthogonal A-trails. Then v(H) is even.
Proof. E(HR) can be partitioned into two edge disjoint spanning quasi-trees by Corol-
lary 3.9. Denote these two spanning quasi-trees by G1 = (V (HR), E1), G2 = (V (HR), E2),
respectively. Obviously, G1 and G2 are both orientable. Then v(HR) − |E1| + 1 =
2− 2g(G1) and v(HR)− |E2|+ 1 = 2− 2g(G2), where g(G1) and g(G2) are the genera
of G1 and G2, respectively. Hence, |E1| + |E2| = 2v(HR) + 2g(G1) + 2g(G2) − 2. It
follows that e(HR) is even, that is, v(H) is even.
Remark 3.11. Andersen, Bouchet and Jackson [3] obtained the same results as Corollar-
ies 3.9 and 3.10 for graphs embedded in the plane, the projective plane and the torus.
4 Quasi-tree bouquets
Theorem 1.4 and Lemma 3.7 show that quasi-tree bouquets are an important class of ribbon
graphs. In this section, we give a brief characterization of them.
We start by recalling some necessary statements. A ribbon graph is non-orientable if
it contains a ribbon subgraph that is homeomorphic to a Möbius band, and is orientable
otherwise. An edge e of a ribbon graph is a loop if it is incident with exactly one vertex.
A loop is non-orientable if together with its incident vertex it forms a Möbius band, and
is orientable otherwise. Two loops e and f are interlaced if they are met in the cyclic
order efef when travelling round the boundary of a vertex. A loop e at the vertex of a
bouquet G is trivial if there is no loop in G which interlaces with e. The signed rotation of
a bouquet is a cyclic ordering of the half-edges at the vertex and if the edge is orientable,
then we give the same sign to the corresponding two half-edges, and give the different signs
otherwise. See Figure 13 for an example. Suppose P = p1p2 · · · pk is a string. Then we
call −P = (−pk) · · · (−p2)(−p1) the inverse of P . Operations 1 and 2 are the moves on
bouquets defined in Figure 14 and Figure 15, respectively. Operation 3 is deleting a pair
of interlaced orientable loops and operation 4 is deleting a trivial non-orientable loop as
shown in Figure 16 and Figure 17, respectively. Note that operations 1, 2, 3 and 4 do not
change the number of boundary components.
Theorem 4.1. Let G be a bouquet. Then G is a quasi-tree bouquet if and only if there is a
sequence of operations 1, 2, 3 and 4 which change the signed rotation of G to be empty.
Proof. The sufficiency is easily verified. To prove the necessity, the result is easily verified
when E(G) = ∅, so assume that this is not the case. Then there are following two cases.
Case 1: If there exists a non-orientable loop r, we assume that the signed rotation of G is
IrJ(−r)P. By a sequence of operation 2, we have I(−J)r(−r)P . Hence, we get a signed
rotation I(−J)P by operation 4.
Q. Yan and X. Jin: A-trails of embedded graphs and twisted duals 283
Figure 13: The signed rotation of the bouquet is ab(−a)cb(−c)dd.
Figure 14: Operation 1. Change the signed rotation from AaBba to AabBa.
Figure 15: Operation 2. Change the signed rotation from AaBb(−a) to A(−b)aB(−a).
284 Ars Math. Contemp. 22 (2022) #P2.06 / 271–286
Figure 16: Operation 3. Change the signed rotation from Aabab to A.
Figure 17: Operation 4. Change the signed rotation from Aa(−a) to A.
Q. Yan and X. Jin: A-trails of embedded graphs and twisted duals 285
Case 2: Otherwise, there exists a pair of interlaced orientable loops e, f . Assume that the
signed rotation of G is IeJfPeQfM. By a sequence of operation 1, we have
IeJfPeQfM ⇔ IefPeQfJM ⇔ IefeQPfJM ⇔ IQPefefJM.
Then by operation 3, we get a signed rotation IQPJM.
Note that both Case 1 and Case 2 induce a shorter signed rotation. By repeating the
above operations, we can reduce the signed rotation of G until it is empty.
Remark 4.2. A bouquet with signed rotation AxyB(−x)(−y)C is not a quasi-tree bou-
quet since AxyB(−x)(−y)C ⇔ Axx(−B)y(−y)C.
We now present an algorithm to get the number of boundary components of any bouquet
G in terms of signed rotations.
Algorithm 1 Calculate the number of boundary components of any bouquet.
1: Input The signed rotation R of a bouquet G.
2: Let a := 1.
3: Step 1. If R = ∅, then stop and output the number of boundary components of G is a.
4: Step 2. Otherwise, there are three cases.
5: if there exists i such that R = AiiB then
6: Let R := AB, a := a+ 1. Return to Step 1.
7: else if there exists r such that R = IrJ(−r)P then
8: Let R := I(−J)P, a := a. Return to Step 1.
9: else
10: Find a pair of interlaced loops e, f such that R = IeJfPeQfM.
Let R := IQPJM, a := a. Return to Step 1.
Example 4.3. A bouquet with signed rotation 13214234 is not a quasi-tree bouquet. Since
there is a pair of interlaced loops 1, 3, we get a shorter signed rotation 4224. A bouquet
with signed rotation
182(−1)34325(−4)756867
is a quasi-tree bouquet. Since
182(−1)34325(−4)756867 1,(−1)−→ (−2)(−8)34325(−4)756867 (−2),2−→
(−3)(−4)(−3)85(−4)756867 (−3),(−4)−→ 85756867 8,7−→ 6565 6,5−→ ∅.
Proposition 4.4. Let G be an orientable bouquet. If G is a quasi-tree bouquet, then e(G)
is even.
Proof. It follows immediately from Euler’s formula.
Proposition 4.5. Let G be a quasi-tree bouquet. If there exists A ⊆ E(G) such that
(V (G), A) and (V (G), Ac) are plane graphs, then |A| = |Ac|.
286 Ars Math. Contemp. 22 (2022) #P2.06 / 271–286
Proof. Note that the vertex boundaries and face boundaries of Gδ(A) correspond to the face
boundaries of (V (G), A) and (V (G), Ac), respectively. It follows that v(Gδ(A)) = |A|+1
and f(Gδ(A)) = |Ac|+1, that is, Gδ(A) is a plane graph. Then E(Gδ(A)) can be partitioned
into two edge disjoint spanning trees by Lemma 3.7. Hence,
e(Gδ(A)) = 2(v(Gδ(A))− 1) = 2|A| = e(G) = |A|+ |Ac|,
that is, |A| = |Ac|.
Example 4.6. A bouquet G with signed rotation 121324356465 is not a quasi-tree bou-
quet. This follows from the fact that (G, {1, 3, 5, 6}) and (G, {2, 4}) are plane graphs, but
|{1, 3, 5, 6}| ≠ |{2, 4}|.
References
[1] L. Abrams and J. A. Ellis-Monaghan, New dualities from old: Generating geometric,
Petrie, and Wilson dualities and trialities of ribbon graphs, 2019, arXiv:1901.03739v1
[math.CO].
[2] L. D. Andersen, H. Fleischner and S. Regner, Algorithms and outerplanar conditions for
A-trails in plane Eulerian graphs, Discrete Appl. Math. 85 (1998), 99–112, doi:10.1016/
s0166-218x(97)00141-8.
[3] L. D. v. Andersen, A. Bouchet and B. Jackson, Orthogonal A-trails of 4-regular graphs
embedded in surfaces of low genus, J. Comb. Theory Ser. B 66 (1996), 232–246, doi:
10.1006/jctb.1996.0017.
[4] S. Chmutov, Generalized duality for graphs on surfaces and the signed Bollobás–Riordan poly-
nomial, J. Comb. Theory Ser. B 99 (2009), 617–638, doi:10.1016/j.jctb.2008.09.007.
[5] J. A. Ellis-Monaghan and I. Moffatt, Twisted duality for embedded graphs, Trans. Am. Math.
Soc. 364 (2012), 1529–1569, doi:10.1090/s0002-9947-2011-05529-7.
[6] J. A. Ellis-Monaghan and I. Moffatt, Graphs on Surfaces, Springer, New York, 2013, doi:
10.1007/978-1-4614-6971-1.
[7] A. Kotzig, Eulerian lines in finite 4-valent graphs and their transformations, in: Theory of
Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968 pp. 219–230.
[8] S. Lins, B. Richter and H. Shank, The Gauss code problem off the plane, Aequationes Math.
33 (1987), 81–95, doi:10.1007/bf01836154.
[9] M. Metsidik, Characterization of some properties of ribbon graphs and their partial duals,
Ph.D. thesis, Xiamen University, 2017.
[10] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Studies in the Mathematical
Sciences, Johns Hopkins University Press, Baltimore, MD, 2001, https://www.sfu.ca/
˜mohar/Book.html.
[11] A. Morse, W. Adkisson, J. Greene, D. Perry, B. Smith, J. Ellis-Monaghan and G. Pang-
born, DNA origami and unknotted A-trails in torus graphs, J. Knot Theory Ramif. 29 (2020),
2050041, 26, doi:10.1142/s0218216520500418.
[12] R. B. Richter, Spanning trees, Euler tours, medial graphs, left-right paths and cycle spaces,
Discrete Math. 89 (1991), 261–268, doi:10.1016/0012-365x(91)90119-m.
[13] A. Žitnik, Plane graphs with Eulerian Petrie walks, volume 244, pp. 539–549, 2002, doi:10.
1016/s0012-365x(01)00061-9.
[14] S. E. Wilson, Operators over regular maps, Pac. J. Math. 81 (1979), 559–568, http:
//projecteuclid.org/euclid.pjm/1102785296.