ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P1.02 / 23–39
https://doi.org/10.26493/1855-3974.2242.842
(Also available at http://amc-journal.eu)
Z-oriented triangulations of surfaces
Adam Tyc *
Institute of Mathematics, Polish Academy of Sciences,
Śniadeckich 8, 00-656 Warszawa, Poland
Received 5 February 2020, accepted 12 April 2021, published online 4 April 2022
Abstract
The main objects of the paper are z-oriented triangulations of connected closed 2-
dimensional surfaces. A z-orientation of a map is a minimal collection of zigzags which
double covers the set of edges. We have two possibilities for an edge – zigzags from the
z-orientation pass through this edge in different directions (type I) or in the same direction
(type II). Then there are two types of faces in a triangulation: the first type is when two
edges of the face are of type I and one edge is of type II and the second type is when all
edges of the face are of type II. We investigate z-oriented triangulations with all faces of the
first type (in the general case, any z-oriented triangulation can be shredded to a z-oriented
triangulation of such type). A zigzag is homogeneous if it contains precisely two edges of
type I after any edge of type II. We give a topological characterization of the homogeneity
of zigzags; in particular, we describe a one-to-one correspondence between z-oriented tri-
angulations with homogeneous zigzags and closed 2-cell embeddings of directed Eulerian
graphs in surfaces. At the end, we give an application to one type of the z-monodromy.
Keywords: Directed Eulerian embedding, triangulation of a surface, zigzag, z-monodromy, z-orien-
tation.
Math. Subj. Class. (2020): 05E45, 52B05
1 Introduction
Petrie polygons are well-known objects described by Coxeter [5] (see also [13]). These are
skew polygons in regular polyhedra such that any two consecutive edges, but not three, are
on the same face. Analogs of Petrie polygons for graphs embedded in surfaces are called
zigzags [7, 10] or closed left-right paths [9, 18]. These are sequences of oriented edges
defined by the rule described above. Zigzags have many applications, for example, they
are successfully exploited to enumerate all combinatorial possibilities for fullerenes [3].
*The author is grateful to Mark Pankov for useful discussions.
E-mail address: atyc@impan.pl (Adam Tyc)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
24 Ars Math. Contemp. 22 (2022) #P1.02 / 23–39
The case when a map, i.e. an embedding of a graph in a surface, has a unique zigzag is very
important [7, 9]. Following [7] we call such maps z-knotted. They have nice homological
properties and are closely connected to the Gauss code problem [6, 9, 11].
The study of zigzags in 3-regular plane graphs, in particular fullerenes, is one of the
main directions of [7]. A large class of z-knotted 3-regular plane graphs is obtained using
a computer. The dual objects, i.e. spherical triangulations, have the same zigzag structure.
Zigzags in triangulations of surfaces (not necessarily orientable) are investigated in [15, 16,
17]. By [17], every such triangulation admits a z-knotted shredding, i.e. it can be modified
to a z-knotted triangulation of the same surface by triangulating of some of its faces.
A z-orientation of a map is a minimal collection of zigzags which double covers the set
of edges [7]. In the z-knotted case, this collection contains only one zigzag and is unique
up to reversing. For every z-orientation we have the following two types of edges: an edge
is of type I if the distinguished zigzags pass through this edge in different directions and
an edge is of type II if they pass through the edge in the same direction. It is not difficult
to prove that for every face in a triangulation with fixed z-orientation one of the following
possibilities is realized: the face contains precisely two edges of type I and the third edge
is of type II (the first type of face) or all edges are of type II (the second type of face).
We observe that every z-oriented triangulation can be shredded to a triangulation where
all faces are of the first type (Section 2). In this paper, we restrict ourself to z-oriented
triangulations with all faces of the first type.
Let Γ be such a triangulation of a surface M . Then the number of edges of type I is
twice the number of edges of type II and we say that a zigzag is homogeneous if it contains
precisely two edges of type I after each edge of type II. Denote by ΓII the subgraph of Γ
formed by all edges of type II. Our first result (Theorem 3.3) states that the following three
conditions are equivalent:
(1) all zigzags of Γ are homogeneous,
(2) ΓII is a closed 2-cell embedding of a simple Eulerian digraph such that every face is
a directed cycle,
(3) each connected component of M \ ΓII is homeomorphic to an open 2-dimensional
disk.
Note that directed Eulerian spherical embeddings are known also as plane alternating
dimaps; they are investigated, for example, in [2, 8, 12]. Directed Eulerian embeddings
in arbitrary surfaces are considered in [1, 4].
We will use the following structural property of Γ (without assumption that the zigzags
are homogeneous): the connected components of M \ ΓII are open disks, cylinders or
Möbius strips (the third type of components can be realized only for the non-orientable
case) and all these possibilities are realized. We show that the existence of cylinders or
Möbius strips contradicts the homogeneity of zigzags.
A z-monodromy of face is a permutation which acts on the oriented edges of this face,
the z-monodromy of an edge e is the first oriented edge of the face which occurs in certain
zigzag after e. By [17], there are precisely 7 types of z-monodromies (M1) – (M7). For
each of the types (M3) – (M5) and (M7) there is a triangulation such that each face has
the z-monodromy of this type. The types (M1) and (M2) are exceptional: all faces with
z-monodromies of each of these types form a forest [16]. The case (M6) cannot be investi-
gated by the methods of [16] and the authors left it as an open problem. It is easy to see that
A. Tyc: Z-oriented triangulations of surfaces 25
each face with the z-monodromy (M6) is of the first type for every z-orientation. Using
this fact, we construct a series of toric triangulations where all faces have z-monodromies
of type (M6).
2 Zigzags and z-orientations of triangulations of surfaces
Let M be a connected closed 2-dimensional surface (not necessarily orientable). A trian-
gulation of M is a 2-cell embedding of a connected simple finite graph in M such that all
faces are triangles [14, Section 3.1]. Then the following assertions are fulfilled:
(1) every edge is contained in precisely two distinct faces,
(2) the intersection of two distinct faces is an edge or a vertex or empty.
Let Γ be a triangulation of M . A zigzag in Γ is a sequence of edges {ei}i∈N satisfying the
following conditions for every natural i:
• ei and ei+1 are distinct edges of a certain face (then they have a common vertex,
since every face is a triangle),
• the faces containing ei, ei+1 and ei+1, ei+2 are distinct and the edges ei and ei+2 are
non-intersecting.
Since Γ is finite, there is a natural number n > 0 such that ei+n = ei for every natural i.
In what follows, every zigzag will be presented as a cyclic sequence e1, . . . , en, where n is
the smallest number satisfying the above condition.
Every zigzag is completely determined by any pair of consecutive edges belonging to
this zigzag and for any distinct edges e and e′ on a face there is a unique zigzag containing
the sequence e, e′. If Z = {e1, . . . , en} is a zigzag, then the reversed sequence Z−1 =
{en, . . . , e1} also is a zigzag. A zigzag cannot contain a sequence e, e′, . . . , e′, e which
implies that Z ̸= Z−1 for any zigzag Z, i.e. a zigzag cannot be self-reversed (see, for
example, [17]). We say that Γ is z-knotted if it contains precisely two zigzags Z and Z−1,
in other words, there is a single zigzag up to reversing.
Example 2.1. Zigzags in the Platonic solids (three of them are triangulations of the sphere)
are skew polygons without self-intersections and are called Petrie polygons.
Example 2.2. Let BPn be the n-gonal bipyramid, where 1, . . . , n denote the consecutive
vertices of the base and the remaining two vertices are denoted by a, b (see Figure 1 for
n = 3).
3
2
1
a
b
.
Figure 1: 3-gonal bipyramid.
26 Ars Math. Contemp. 22 (2022) #P1.02 / 23–39
(a) In the case when n = 2k + 1, the bipyramid BPn is z-knotted. If k is odd, then the
unique (up to reversing) zigzag is
a1, 12, 2b, b3, . . . , a(n− 2), (n− 2)(n− 1), (n− 1)b, bn, n1,
1a, a2, 23, 3b, . . . , a(n− 1), (n− 1)n, nb,
b1, 12, 2a, a3, . . . , b(n− 2), (n− 2)(n− 1), (n− 1)a, an, n1,
1b, b2, 23, 3a, . . . , b(n− 1), (n− 1)n, na.
If k is even, then this zigzag is
a1, 12, 2b, b3, . . . , b(n− 2), (n− 2)(n− 1), (n− 1)a, an, n1,
1b, b2, 23, 3a, . . . , a(n− 1), (n− 1)n, nb,
b1, 12, 2a, a3, . . . , a(n− 2), (n− 2)(n− 1), (n− 1)b, bn, n1,
1a, a2, 23, 3b, . . . , b(n− 1), (n− 1)n, na.
(b) If n = 2k and k is odd, then the bipyramid contains precisely two zigzags (up to
reversing):
a1, 12, 2b, b3, 34, . . . , a(n− 1), (n− 1)n, nb,
b1, 12, 2a, a3, 34, . . . , b(n− 1), (n− 1)n, na
and
a2, 23, 3b, b4, 45, . . . , an, n1, 1b,
b2, 23, 3a, a4, 45, . . . , bn, n1, 1a.
(c) In the case when n = 2k and k is even, there are precisely four zigzags (up to
reversing):
a1, 12, 2b, . . . , b(n− 1), (n− 1)n, na;
b1, 12, 2a, . . . , a(n− 1), (n− 1)n, nb;
a2, 23, 3b, . . . , bn, n1, 1a;
b2, 23, 3a, . . . , an, n1, 1b.
See [15, 17] for more examples of z-knotted triangulations. Examples of z-knotted
fullerenes can be found in [7].
Suppose that Γ contains precisely k distinct zigzags up to reversing. A z-orientation
of Γ is a collection τ consisting of k distinct zigzags such that for each zigzag Z we have
Z ∈ τ or Z−1 ∈ τ . There are precisely 2k distinct z-orientations of Γ. For every z-
orientation τ = {Z1, . . . , Zk} the z-orientation τ−1 = {Z−11 , . . . , Z
−1
k } will be called
reversed to τ . The triangulation Γ with a z-orientation τ will be denoted by (Γ, τ) and
called a z-oriented triangulation.
Let τ be a z-orientation of Γ. For every edge e of Γ one of the following possibilities is
realized:
• there is a zigzag Z ∈ τ such that e occurs in this zigzag twice and other zigzags from
τ do not contain e,
A. Tyc: Z-oriented triangulations of surfaces 27
• there are two distinct zigzags Z,Z ′ ∈ τ such that e occurs in each of these zigzags
only once and other zigzags from τ do not contain e.
In the first case, we say that e is an edge of type I if Z passes through e twice in different
directions; otherwise, e is said to be an edge of type II. Similarly, in the second case: e is
an edge of type I if Z and Z ′ pass through e in different directions or e is an edge of type
II if Z and Z ′ pass through e in the same direction. In what follows, edges of type II will
be considered together with the direction defined by τ . A vertex of Γ is called of type I if it
belongs only to edges of type I; otherwise, we say that this is a vertex of type II.
The following statements hold for any z-orientation τ of Γ.
Lemma 2.3. For each vertex of type II the number of edges of type II which enter this
vertex is equal to the number of edges of type II which leave it.
Proof. The number of times that the zigzags from τ enter a vertex is equal to the number
of times that these zigzags leave this vertex.
Proposition 2.4. For every face of (Γ, τ) one of the following possibilities is realized:
(I) the face contains two edges of type I and the third edge is of type II, see Figure 2(a);
(II) all edges of the face are of type II and form a directed cycle, see Figure 2(b).
A face in a triangulation is said to be of type I or of type II if the corresponding possi-
bility is realized.
(a) (b)
Figure 2: Two types of faces.
Proof of Proposition 2.4. Consider a face whose edges are denoted by e1, e2, e3. Without
loss of generality we can assume that the zigzag containing the sequence e1, e2 belongs to
τ . Let Z and Z ′ be the zigzags containing the sequences e2, e3 and e3, e1, respectively.
Then Z ∈ τ or Z−1 ∈ τ and Z ′ ∈ τ or Z ′−1 ∈ τ . An easy verification shows that for each
of these four cases we obtain (I) or (II).
Example 2.5. If n is odd, then the bipyramid BPn has a unique z-orientation (up to re-
versing), see Example 2.2(a). The edges ai and bi, i ∈ {1, . . . , n} are of type I and the
edges on the base of the bipyramid are of type II. The vertices a, b are of type I and the
vertices on the base are of type II. All faces are of type I. The same happens for the case
when n = 2k and k is odd if the z-orientation is defined by the two zigzags presented in
Example 2.2(b); however, all faces are of type II if we replace one of these zigzags by the
reversed.
28 Ars Math. Contemp. 22 (2022) #P1.02 / 23–39
Example 2.6. Suppose that n = 2k and k is even. Let Z1, Z2, Z3, Z4 be the zigzags from
Example 2.2(c). For the z-orientation defined by these zigzags all faces are of type I. If the
z-orientation is defined by Z1, Z2 and Z−13 , Z
−1
4 , then all faces are of type II. In the case
when the z-orientation is defined by Z1, Z2, Z3 and Z−14 , there exist faces of both types.
Remark 2.7. If we replace a z-orientation by the reversed z-orientation, then the type of
every edge does not change (but all edges of type II reverse the directions), consequently,
the types of vertices and faces also do not change. For z-knotted triangulations there is a
unique z-orientation (up to reversing) and we can determine the types of edges, vertices
and faces without attaching to a z-orientation [15].
A triangulation Γ′ of M is a shredding of the triangulation Γ if it is obtained from Γ
by triangulating some faces of Γ such that all new vertices are contained in the interiors of
these faces.
Proposition 2.8. Any z-oriented triangulation admits a z-oriented shredding with all faces
of type I.
Proof. Let F be a face of type II in a z-oriented triangulation (Γ, τ) and let e1, e2, e3 be
edges of F . Suppose that the edges of F are oriented as in Figure 3 and denote by σ the
permutation (1, 2, 3).
e3 e2
e1
e3 e2
e1
e′3e
′
2
e′1
Figure 3: Triangulation of faces of type II.
Zigzags from τ passes through F precisely three times, so the face F separates them
into 3 segments of type
eσ−1(i), ei, Xij , ej , eσ(j),
where i, j ∈ {1, 2, 3} and the sequence Xij is a maximal part of a zigzag formed by edges
occuring between ei and ej . Let X be the set of all such sequences Xij for F and the
z-orientation τ . Note that every Xij ∈ X is completely determined by the beginning edge
ei and the final edge ej . Now, we triangulate the face F by adding a vertex in the interior
of F and three edges connecting this vertex with the vertices of F . We denote this new
triangulation by Γ′ and write e′i for the new edge if it does not has a common vertex with
ei (see Figure 3). Observe that for any i ∈ {1, 2, 3} there exists a zigzag in Γ′ containing a
subsequence of the form
ei, e
′
σ−1(i), e
′
i, eσ−1(i), Xσ−1(i)j
for certain j ∈ {1, 2, 3} and Xσ−1(i)j ∈ X . The edge ej which occurs in the zigzag directly
after this subsequence is the same as the edge after Xσ−1(i)j in (Γ, τ), since Xσ−1(i)j does
not contain edges of F . Therefore, zigzags of Γ′ related to the three faces not contained in
A. Tyc: Z-oriented triangulations of surfaces 29
Γ pass through the edges coming from Γ in the same way as zigzags from τ . This implies
the existence of a z-orientation of Γ′ such that all edges from Γ do not change their types
and the three new faces of Γ′ contained in F are of type I. Recursively, we eliminate all
faces of type II from (Γ, τ) and come to a z-oriented shredding of Γ with all faces of type
I and such that the type of any edge from (Γ, τ) is preserved.
3 Homogeneous zigzags in triangulations with faces of type I
In this section, we will always suppose that Γ is a triangulation with fixed z-orientation τ
such that all faces in Γ are of type I, i.e. each face contains precisely two edges of type I and
the third edge is of type II. If m is the number of faces, then there are precisely m edges
of type I and m/2 edges of type II. In other words, the number of edges of type I is twice
the number of edges of type II. We say that a zigzag of Γ is homogeneous if it is a cyclic
sequence {ei, e′i, e′′i }ni=1, where each ei is an edge of type II and all e′i, e′′i are edges of type
I. If a zigzag is homogeneous, then the reversed zigzag also is homogeneous. Denote by
ΓII the subgraph of Γ formed by all vertices and by all edges of type II.
Example 3.1. The zigzags of Γ = BPn are homogeneous if n is odd (the z-knotted case)
or n is even and the z-orientation is defined by the two zigzags from Example 2.2(b) or by
the four zigzags from Example 2.2(c). Only a and b are vertices of type I and ΓII is the
directed cycle formed by the edges of the base of the bipyramid. Conversely, if all zigzags
of Γ are homogeneous and there are precisely two vertices of type I, then Γ is a bipyramid
(this statement is an easy consequence of Theorem 3.3 which will be presented later).
Example 3.2. Let Γ′ be a triangulation of M with a z-orientation such that all faces are of
type II (see [16, Example 4] for a z-knotted triangulation of S2 whose faces are of type II).
As in the proof of Proposition 2.8, we consider the shredding Γ′′ of Γ′ which is obtained
by adding a vertex in the interior of each face and three edges connecting this vertex with
the vertices of the face. This triangulation Γ′′ admits a z-orientation such that all faces are
of type I. Every zigzag e1, e2, e3, . . . in Γ′ is extended to a zigzag
e1, e
′
1, e
′′
1 , e2, e
′
2, e
′′
2 , e3, . . .
in Γ′′ which passes through edges of Γ′ in the opposite directions. All ei are of type II and
all e′i and e
′′
i are of type I. So, all zigzags in Γ
′′ are homogeneous.
An Eulerian digraph is a connected digraph such that indegree equals outdegree for
every vertex.
Theorem 3.3. The following three conditions are equivalent:
(1) All zigzags of Γ are homogeneous.
(2) ΓII is a closed 2-cell embedding of a simple Eulerian digraph such that every face is
a directed cycle.
(3) Each connected component of M \ ΓII is homeomorphic to an open 2-dimensional
disk.
The implication (2) ⇒ (3) is obvious. The implications (1) ⇒ (2) and (3) ⇒ (1) will
be proved in Section 4 and Section 5, respectively.
30 Ars Math. Contemp. 22 (2022) #P1.02 / 23–39
4 Proof of the implication (1) ⇒ (2) in Theorem 3.3
Now, we generalize the construction described in Proposition 2.8 and Example 3.2. Let Γ′
be a closed 2-cell embedding of a connected finite simple graph in the surface M . Then all
faces of Γ′ are homeomorphic to a closed 2-dimensional disk. For each face F we take a
point vF belonging to the interior of F . We add all vF to the vertex set of Γ′ and connect
each vF with every vertex of F by an edge. We obtain a triangulation of M which will be
denoted by T(Γ′).
The assumption that our 2-cell embedding is closed cannot be omitted. Indeed, if a
certain face of Γ′ is not homeomorphic to a closed 2-dimensional disk, then there is a pair
of vertices connected by a double edge and T(Γ′) is not a triangulation in our sense.
Proposition 4.1. If all zigzags of Γ are homogeneous, then ΓII is a closed 2-cell embedding
of a simple Eulerian digraph such that every face is a directed cycle and Γ = T(ΓII).
Conversely, if Γ′ is a closed 2-cell embedding of a simple Eulerian digraph and every face
is a directed cycle, then the triangulation T(Γ′) admits a unique z-orientation such that all
zigzags of T(Γ′) are homogeneous and Γ′ is the subgraph of T(Γ′) formed by all vertices
and edges of type II.
Proof. (I): Let v be a vertex of Γ. Consider all faces containing v and take the edge on each
of these faces which does not contain v. All such edges form a cycle which will be denoted
by C(v).
Suppose that all zigzags of Γ are homogeneous and consider any edge e1 of type II. Let
v1 and v2 be the vertices of this edge such that e1 is directed from v1 to v2. We choose
one of the two faces containing e1 and take in this face the vertex v which does not belong
to e1. Let e′1 and e
′′
1 be the edges which contain v and occur in a certain zigzag Z ∈ τ
immediately after e1, see Figure 4. Denote by e2 the third edge of the face containing e′1
and e′′1 . This edge contains v2 and another one vertex, say v3. Since Z is homogeneous,
the edges e′1 and e
′′
1 are of type I, and consequently, e2 is of type II. The zigzag which
goes through e′1 from v to v2 belongs to τ (this follows easily from the fact that Z goes
through e′1 in the opposite direction and e
′
1 is an edge of type I). The latter guarantees that
the edge e2 is directed from v2 to v3. By our assumption, the edge e3 which occurs in Z
immediately after e′1 and e
′′
1 is of type II. This edge is directed from v3 to a certain vertex
v4. So, e1, e2, e3 are consecutive edges of the cycle C(v) and each ei is directed from vi
to vi+1. Consider the zigzag from τ which contains the sequence e2, e′′1 . The next edge
in this zigzag connects v and v4 (the zigzag goes from v to v4). Let e4 be the edge which
occurs in the zigzag after it. Then e4 is an edge of type II (by our assumption), it belongs
to C(v) and leaves v4. Recursively, we establish that C(v) is a directed cycle formed by
edges of type II and every edge containing v is of type I, i.e. v is a vertex of type I. Now,
v
v4
v3
v2
v1
e1
e2 e3
e4
e′1
e′′1
s
Figure 4: Cycle of edges of type II.
A. Tyc: Z-oriented triangulations of surfaces 31
we consider the other face containing e1 and take the vertex v′ of this face which does not
belong to e1. Using the same arguments, we establish that v′ is a vertex of type I and C(v′)
is a directed cycle formed by edges of type II.
For every vertex v of type I we can take a face containing v and the edge of this face
which does not contain v. This edge is of type II (since the remaining two edges of the face
are of type I). The above arguments show that the following assertions are fulfilled:
(1) vertices of type I exist and for every such vertex v the cycle C(v) is a directed cycle
formed by edges of type II;
(2) for every edge of type II there are precisely two vertices v and v′ of type I such that
this edge is contained in the cycles C(v) and C(v′).
Similarly, for every edge e of type I we take a face containing e; this face contains an edge
of type II which implies that e connects vertices of different types.
Consider ΓII. Any two vertices of type II in Γ can be connected by a path formed by
edges of type II which means that ΓII is connected. Indeed, if a path between two vertices
of type II goes through a vertex v of type I, then the edge going into v and the edge leaving
v are incident to vertices in the same cycle C(v) and so we can rewrite that part of the path
to use edges from C(v) instead of the edges through v. It is easy to see that ΓII is a 2-cell
embedding of a simple digraph such that every face is the directed cycle C(v) for a certain
vertex v of type I; in particular, this 2-cell embedding is closed. Lemma 2.3 implies that
ΓII is an Eulerian digraph. The equality Γ = T(ΓII) is obvious.
The following remark will be used to prove the second part of the theorem. The con-
ditions (1) and (2) guarantee that every zigzag of Γ containing an edge of type II is homo-
geneous. Recall that the number of edges of type I is twice the number of edges of type
II. This implies that there is no zigzag containing edges of type I only (since every edge
occurs twice in a unique zigzag from τ or it occurs ones in precisely two distinct zigzags
from τ ). Therefore, every zigzag of Γ is homogeneous if (1) and (2) hold.
(II): Suppose that Γ′ is a closed 2-cell embedding of a simple Eulerian digraph such
that every face is a directed cycle.
Let e1, . . . , en be the directed cycle formed by all edges of a certain face of Γ′. For
every i ∈ {1, . . . , n} we define j(i) = i + 2(modn) and denote by e′i and e′′i the edges
containing the vertex vF in T(Γ′) and intersecting ei and ej(i), respectively. Consider the
zigzag of T(Γ′) which contains the sequence ei, e′i, e
′′
i , ej(i). It passes through ei and ej(i)
according to the directions of these edges; and the same holds for every edge of Γ′ which
occurs in this zigzag. Such a zigzag exists for any pair formed by a face of Γ′ and an
edge on this face. The collection of all such zigzags is a z-orientation of T(Γ′) with the
following properties: all edges of Γ′ are of type II and every vF is a vertex of type I. This
implies that T(Γ′) satisfies the conditions (1) and (2) which gives the claim.
Note that the second part of Proposition 4.1 will be used to prove the implication
(3) ⇒ (1).
5 Structure of triangulations with faces of type I
In this section, we describe some structural properties of z-oriented triangulations with
faces of type I. As an immediate consequence we obtain the implication (3) ⇒ (1).
32 Ars Math. Contemp. 22 (2022) #P1.02 / 23–39
As above, we suppose that (Γ, τ) is a z-oriented triangulation of M , where all faces
are of type I. As above, we denote by ΓII the subgraph of Γ consisting of all vertices
and all edges of type II. From the previous section it follows that if the zigzags of (Γ, τ)
are homogeneous, then connected components of M \ ΓII are homeomorphic to open 2-
dimensional disks. Now, we describe the general case.
Theorem 5.1. The following assertions are fullfiled:
(1) Connected components of M \ΓII are homeomorphic to an open 2-dimensional disk,
an open Möbius strip or an open cylinder.
(2) A connected component of M \ ΓII contains a vertex of type I if and only if it is an
open 2-dimensional disk; such a vertex of type I is unique.
Proof. Consider two distinct edges e0 and e1 of type I contained in a certain face F1.
There is precisely one face containing e1 and distinct from F1. Denote this face by F2 and
write e2 for the other edge of type I on F2. Recursively, we construct sequences of edges
{ei}i∈N∪{0} and faces {Fi}i∈N such that ei−1 is the common edge of Fi−1, Fi for every
i ∈ N. For any pair of the faces Fi−1, Fi we distinguish the following two cases presented
in Figure 5. In the first case, the edges of type II of Fi−1 and Fi have a common vertex
(Figure 5(a)). In the second case (Figure 5(b)), the edges of type II are disjoint.
ei−2
ei−1
ei
Fi−1 Fi
(a)
Fi
ei−2
ei−1
ei
Fi−1
(b)
Figure 5: Two possibilities of adjacency for faces of type I.
Let n be the smallest natural number such that en = e0 (such a number exists by
finiteness). Therefore, the above sequences can be considered as cyclic sequences {ei}ni=1
and {Fi}ni=1. The union F =
⋃n
i=1 Fi will be called a component of (Γ, τ). The boundary
of F consists of (not necessarily all) edges of type II belonging to faces Fi.
Denote by eIIi the edge of type II belonging to Fi. We take n disjoint closed triangles
T1, T2, . . . , Tn. For any i = 1, 2, . . . , n there is a homeomorphism hi : Fi → Ti transfer-
ring any vertex and any edge of Fi to a vertex and an edge of Ti, respectively. We identify
hi(ei) and hi+1(ei) for any i in such a way that for every vertex v of ei the vertices hi(v)
and hi+1(v) are identified. We get a 2-dimensional surface T with boundary. The bound-
ary of T is the union of the images of all edges of type II, i.e. ∂T =
⋃n
i=1 hi(e
II
i ). Note
that F is not necessarily a surface (since it is possible that for distinct i, j the edges eIIi , eIIj
have a common vertex). The interior of surface T is homeomorphic to one of the con-
nected components of M \ ΓII and F can be obtained from T by gluing of some parts of
the boundary.
Suppose that hi(ei) and hi+1(ei) are identified only for i = 1, 2, . . . , n − 1 (but not
h1(e0) and hn(en) from T1 and Tn, respectively). Then we get a space homeomorphic to
A. Tyc: Z-oriented triangulations of surfaces 33
a closed 2-dimensional disk whose boundary contains h1(e0), hn(en). Now, to complete
the construction of T , we have to glue h1(e0) and hn(en). Precisely one of the following
possibilities is realized:
• A union of these sides is connected and by gluing of them we obtain that T is home-
omorphic to a closed 2-dimensional disk (Figure 6(1)).
• The sides are disjoint and by identification of them we get a surface homeomorphic
to a closed Möbius strip (Figure 6(2)) or a closed cylinder (Figure 6(3)).
h1(e0) hn(en)
...
(1)
h1(e0) . . . hn(en)
(2)
h1(e0) . . . hn(en)
(3)
Figure 6: Closed disk, closed Möbius strip and closed cylinder.
Let vi be the vertex of Ti corresponding to the vertex of Fi not belonging to the edge
eIIi . In the first case, the images of edges of type I have the common vertex which is the
image of all hi(vi); it is clear that this vertex corresponds to the vertex of type I from F ,
see Figure 6(1). In the remaining cases, any vertex hi(vi) is contained in the boundary of
T and correspond to a certain vertex of ΓII (see Figure 6(2) and 6(3)). So, we obtained the
statements (1) and (2).
If a connected component of M \ ΓII is homeomorphic to an open 2-dimensional disk,
then the corresponding component of (Γ, τ) is homeomorphic to a closed 2-dimensional
disk (if this component has some identifications at the boundary, then the vertex of type I
in this component is joined by a double edge to a certain vertex at the boundary which is
impossible, since we work with embeddings of simple graphs).
Proof of (3) ⇒ (1) in Theorem 3.3. Assume that each connected component of M \ΓII is a
disk. By the above remark, ΓII is a closed 2-cell embedding. Lemma 2.3 shows that this is
an embedding of simple Eulerian digraph. The second part of Theorem 5.1 states that each
34 Ars Math. Contemp. 22 (2022) #P1.02 / 23–39
disk contains a unique vertex of type I; as in the proof of Theorem 5.1 we establish that its
boundary is an oriented cycle. We have Γ = T(ΓII) and the second part of Proposition 4.1
gives the claim.
The following three examples show that all possibilities for connected components of
M \ ΓII are realized.
Example 5.2. Consider the following triangulation Γ of a torus T = S1×S1 (see Figure 7).
The triangulation Γ admits the z-orientation such that all faces are of type I. The subgraph
ΓII has two connected components which are 6-cycles and T\ΓII consists of two connected
components homeomorphic to open cylinders (−1, 1)× S1.
3
45
0
1 2
0
12
3
4 5
Figure 7: Toric triangulation.
In a similar way, we can construct a z-oriented toric triangulation with connected com-
ponents of T \ ΓII which are open cylinders of arbitrary length.
Example 5.3. Let n ∈ N and let Γ be the triangulation of a real projective plane obtained
by gluing of boundaries of a Möbius strip and a closed 2-dimensional disk (see Figure 8).
According to the corresponding z-orientation all faces are of type I and the graph ΓII con-
sists of all edges marked by the double arrows and their vertices. Then RP2 \ ΓII has two
connected components. One of them is homeomorphic to an open 2-dimensional disk and
the remaining to an open Möbius strip.
Example 5.4. Suppose that Γ is the triangulation of a sphere obtained by the gluing of
the two disks whose boundaries are cycles e1, e2, . . . , e6 (see Figure 9). There is a z-
orientation τ such that all faces are of type I. Then S2 \ ΓII has precisely four connected
components: three components are homeomorphic to an open 2-dimensional disk and the
remaining to an open cylinder. The components of (Γ, τ) corresponding to the first three
connected components are closed 2-dimensional disks. The fourth component of (Γ, τ) is
homeomorphic to a closed cylinder S1 × D1, where two points at one of the connected
components of the boundary are glued.
A. Tyc: Z-oriented triangulations of surfaces 35
. . .
n+1 n+2 n+3 n+4 2n
e e
1 2 3 4 n
4
3
2
1
2nn+4
n+3
n+2
n+1
n
...
...
Figure 8: Projective plane triangulation.
e4
e5
e6
e1
e2
e3
e4
e5
e6
e1
e2
e3
Figure 9: Spherical triangulation.
6 Relations to z-monodromies
Let F be a face in Γ whose vertices are a, b, c. Consider the set Ω(F ) of all oriented edges
of F
Ω(F ) = {ab, bc, ca, ac, cb, ba},
where xy is the edge from x ∈ {a, b, c} to y ∈ {a, b, c}. If e = xy then we write yx by
−e. Denote by DF the following permutation of the set Ω(F )
(ab, bc, ca)(ac, cb, ba).
36 Ars Math. Contemp. 22 (2022) #P1.02 / 23–39
The z-monodromy (see [16, 17]) of the face F is the permutation MF defined as follows.
For any e ∈ Ω(F ) we take e0 ∈ Ω(F ) such that DF (e0) = e and consider the zigzag
containing the sequence e0, e. We define MF (e) as the first element of Ω(F ) contained in
this zigzag after e.
By [17, Theorem 4.4], there are the following possibilities for the z-monodromy MF
and each of them is realized:
(M1) MF is the identity,
(M2) MF = DF ,
(M3) MF = (−e1, e2, e3)(−e3,−e2, e1),
(M4) MF = (e1,−e2)(e2,−e1), where e3 and −e3 are fixed points,
(M5) MF = (DF )−1,
(M6) MF = (−e1, e3, e2)(−e2,−e3, e1),
(M7) MF = (e1, e2)(−e1,−e2), where e3 and −e3 are fixed points,
where (e1, e2, e3) is one of the cycles in DF .
Let Gi be the subgraph of the dual Γ∗ formed by vertices corresponding to faces in Γ
whose z-monodromies are of type (Mi), two vertices of Gi are adjacent if they are adjacent
in Γ∗. By [16, Theorem 1], the subgraphs G1 and G2 are forests. For (M3), (M4), (M5)
and (M7) the above statement fails: z-monodromies of all faces of the bipyramid BPn are
of type
• (M3) for n = 2k + 1 where k is odd,
• (M4) for n = 2k + 1 where k is even,
• (M7) for n = 2k where k is odd,
• (M5) for n = 2k where k is even.
Proposition 6.1. If MF is (M6), then F is of type I for any z-orientation of Γ.
Proof. Let e1, e2, e3 be consecutive oriented edges of the face F . We suppose that the
z-monodromy of F is (M6), i.e.
MF = (−e1, e3, e2)(−e2,−e3, e1).
There are precisely two zigzags (up to reversing) which contain F
e1, e2, . . . ,−e1,−e3, . . . and e2, e3, . . . ;
since the edge corresponding to the pair {e1,−e1} is passed in two different directions by
the same zigzag, then it is of type I for any orientation of the zigzag. Therefore, F is of
type I for any z-orientation.
Lemma 6.2. Let F be a face in (Γ, τ) such that there are precisely two zigzags from τ
which contain edges from F . Then the following assertions are fulfilled:
A. Tyc: Z-oriented triangulations of surfaces 37
(1) There is a unique edge e ∈ F which occurs in one of these zigzags twice.
(2) The type of e does not depend on the choice of z-orientation.
(3) If e is of type I, then MF is (M6). If e is of type II, then MF is (M7).
Proof. (1): Any face occurs precisely thrice, as a pair of its adjacent edges, in zigzags from
the z-orientation τ . By the assumption, there are precisely two zigzags from τ which pass
through our face. This is possible only when one of these zigzags passes through it once
and the second twice.
(2): The edge e can occur in the same zigzag twice in two ways: the zigzag passes
through e the first time in one of directions and the second time in the opposite (type I) or
the zigzag passes through e twice in the same direction (type II). It is easy to see that the
type of e is the same for any z-orientation of Γ.
(3): By [17, Remark 4.9] the z-monodromy of the face F is (M6) or (M7). In the case
(M6) the statement follows from Proposition 6.1. Let e1, e2, e3 be consecutive edges of F
and MF be of type (M7), i.e.
MF = (e1, e2)(−e1,−e2).
In this case, F occurs twice in the zigzag
e2, e3, . . . , e3, e1, . . .
and e3 is of type II for any z-orientation of Γ.
Now, we can construct a class of toric triangulations, where z-monodromies are of type
(M6) for all faces. Our arguments are based on Lemma 6.2.
Example 6.3. Let n,m be odd numbers not less than 3 and let Γ0 be a n ×m grid where
the opposite sides are identified. Then Γ0 can be embedded into a torus in the natural way.
Suppose that Γ = T(Γ0) (see Figure 10 for the case n = m = 3).
e4 e5 e6
e4 e5 e6
e1
e2
e3
e1
e2
e3
Figure 10: Toric triangulation related to 3× 3 grid.
Each zigzag of Γ determines a band formed by n or m squares from the grid (see
Figure 11 for a band consisting of 5 squares) and passes through each face of this band
twice.
38 Ars Math. Contemp. 22 (2022) #P1.02 / 23–39
Figure 11: Band consisting of 5 squares.
Observe that the edges common for two consecutive squares from the grid are passed
twice (they marked on Figure 11 by the bold line) and are of type I for any z-orientation.
Remaining edges are passed by the zigzag once. Therefore, all edges of subgraph Γ0 are
of type I and all faces of Γ are of type I for any z-orientation. It is clear that any edge
incident to a vertex in the interior of a square occurs once in two different zigzags. Thus,
for any face of Γ there are precisely two zigzags which pass it. Lemma 6.2 guarantees that
z-monodromies of all faces of Γ are (M6).
ORCID iDs
Adam Tyc https://orcid.org/0000-0003-4870-5731
References
[1] C. P. Bonnington, M. Conder, M. Morton and P. McKenna, Embedding digraphs on orientable
surfaces, J. Comb. Theory Ser. B 85 (2002), 1–20, doi:10.1006/jctb.2001.2085.
[2] C. P. Bonnington, N. Hartsfield and J. Širáň, Obstructions to directed embeddings of Eulerian
digraphs in the plane, Eur. J. Comb. 25 (2004), 877–891, doi:10.1016/j.ejc.2003.06.006.
[3] G. Brinkmann and A. W. M. Dress, PentHex puzzles: a reliable and efficient top-down approach
to fullerene-structure enumeration, Adv. in Appl. Math. 21 (1998), 473–480, doi:10.1006/aama.
1998.0608.
[4] Y. Chen, J. L. Gross and X. Hu, Enumeration of digraph embeddings, Eur. J. Comb. 36 (2014),
660–678, doi:10.1016/j.ejc.2013.10.003.
[5] H. S. M. Coxeter, Regular Polytopes, Dover Publications, New York, 3rd edition, 1973.
[6] H. Crapo and P. Rosenstiehl, On lacets and their manifolds, Discrete Math. 233 (2001), 299–
320, doi:10.1016/s0012-365x(00)00248-x.
[7] M.-M. Deza, M. Dutour Sikirić and M. I. Shtogrin, Geometric Structure of Chemistry-Relevant
Graphs: Zigzags and Central Circuits, volume 1 of Forum for Interdisciplinary Mathematics,
Springer, New Delhi, 2015, doi:10.1007/978-81-322-2449-5.
[8] G. E. Farr, Minors for alternating dimaps, Q. J. Math. 69 (2018), 285–320, doi:10.1093/qmath/
hax039.
[9] C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Graduate Texts in Mathemat-
ics, Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9.
[10] S. Lins, Graph-encoded maps, J. Comb. Theory Ser. B 32 (1982), 171–181, doi:10.1016/
0095-8956(82)90033-8.
[11] S. Lins, E. Oliveira-Lima and V. Silva, A homological solution for the Gauss code problem in
arbitrary surfaces, J. Comb. Theory Ser. B 98 (2008), 506–515, doi:10.1016/j.jctb.2007.08.007.
A. Tyc: Z-oriented triangulations of surfaces 39
[12] T. A. McCourt, Growth rates of groups associated with face 2-coloured triangulations and
directed Eulerian digraphs on the sphere, Electron. J. Comb. 23 (2016), #P1.51 (23 pages),
doi:10.37236/5410.
[13] P. McMullen and E. Schulte, Abstract Regular Polytopes, volume 92 of Encyclopedia of Math-
ematics and its Applications, Cambridge University Press, Cambridge, 2002, doi:10.1017/
cbo9780511546686.
[14] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Studies in the Mathematical
Sciences, Johns Hopkins University Press, Baltimore, MD, 2001.
[15] M. Pankov and A. Tyc, Connected sums of z-knotted triangulations, Eur. J. Comb. 80 (2019),
326–338, doi:10.1016/j.ejc.2018.02.010.
[16] M. Pankov and A. Tyc, On two types of z-monodromy in triangulations of surfaces, Discrete
Math. 342 (2019), 2549–2558, doi:10.1016/j.disc.2019.05.030.
[17] M. Pankov and A. Tyc, z-knotted triangulations of surfaces, Discrete Comput. Geom. 66
(2021), 636–658, doi:10.1007/s00454-020-00182-3.
[18] H. Shank, The theory of left-right paths, in: A. P. Street and W. D. Wallis (eds.), Combina-
torial Mathematics III, Springer-Verlag, Berlin-New York, volume 452 of Lecture Notes in
Mathematics, 1975 pp. 42–54, doi:10.1007/bfb0069542, proceedings of the Third Australian
Conference, held at the University of Queensland, St. Lucia, May 16 – 18, 1974.