# Computation of toroidal Schnyder woods made simple and fast: from theory to practice

Luca Castelli Aleardi, Eric Fusy, Jyh-Chwen Ko, Razvan-Stefan Puscasu

► To cite this version:

Luca Castelli Aleardi, Eric Fusy, Jyh-Chwen Ko, Razvan-Stefan Puscasu. Computation of toroidal Schnyder woods made simple and fast: from theory to practice. 2025. hal-05027238

HAL Id: hal-05027238

https://hal.science/hal-05027238v1

Preprint submitted on 9 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Computation of toroidal Schnyder woods made
simple and fast: from theory to practice

Luca Castelli Aleardi*

Eric Fusy†

Jyh-Chwen Ko‡

Razvan-Stefan Puscasu§

April 9, 2025

Abstract

We consider the problem of computing Schnyder woods for graphs embedded on the torus. We design simple linear-time algorithms based on canonical orderings that compute toroidal Schnyder woods for simple toroidal triangulations. The Schnyder woods computed by one of our algorithm are crossing and satisfy an additional structural property: at least two of the mono-chromatic components of the Schnyder wood are connected. We also exhibit experimental results empirically confirming three conjectures involving the structure of toroidal and higher genus Schnyder woods.

# 1 Introduction

Graphs embedded on surfaces exhibit many significant structural properties. In the planar case, one of the most elegant characterizations is provided by Schnyder woods [26, 27], a profound combinatorial structure introduced by W. Schnyder to define a new planarity criterion and to design an efficient and elegant straight-line grid drawing algorithm. Schnyder woods lead to a global characterization of planar graphs in terms of spanning trees and have inspired numerous generalizations and applications in various fields, including graph drawing [13, 14, 12], graph encoding, enumerative combinatorics [2, 15], random sampling [24] and plane spanners [4].

The first generalizations [5, 10] of Schnyder woods to non planar graphs were motivated by applications involving graph encoding problems, aiming to preserve their global spanning properties. Since then the study of Schnyder woods

<footnote>*LIX, Ecole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France. amtur-ing@lix.polytechnique.fr</footnote>

<footnote>†LIGM, Université Gustave Eiffel, Champs-sur-Marne, France. eric.fusy@univ-eiffel.fr</footnote>

<footnote>‡LIX, Ecole Polytechnique, Institut Polytechnique de Paris, Palaiseau, France. jyh-chwen.ko@polytechnique.edu</footnote>

<footnote>§École polytechnique fédérale de Lausanne (EPFL) Station Z CH-1015 Lausanne. razvan-stefan.puscasu@epfl.ch</footnote>
and related structures for graphs embedded on toroidal [3, 17, 22, 11, 16, 9, 6]
and higher genus [10, 1, 20, 28] surfaces have attracted a lot of attention. This is
particularly true in the toroidal case, for which some elegant generalizations lead
to applications ranging from graph drawing [17] to bijective encodings [3, 11, 16].

## Toroidal Schnyder woods.

A key property of toroidal triangulations is that the number of edges is exactly three times the number of vertices, by Euler's formula. Gonçalves and Lévêque [17] show how to endow a simple toroidal triangulation with an edge orientation and coloring with three colors<fnref n="1" /> {0, 1, 2} where every vertex has outgoing degree 3 and satisfies a local Schnyder rule (as in the plane). It turns out that the *i*-cycles<fnref n="2" /> are directed, non-contractible and homotopic, and they do not intersect each other. Moreover, any toroidal triangulation admits a crossing Schnyder wood for which every pair of *i*-cycles and *j*-cycles (for *i* ≠ *j*) are crossing, which is particularly relevant for graph drawing applications. Indeed, the crossing condition is crucial for obtaining a periodic straight-line drawing [17] of toroidal maps on a grid of polynomial resolution, which extends the face-counting approach of planar Schnyder drawings [27, 13, 14].

## 1.1 Contribution.

Addressing two questions left open in [17, 22], we design and implement a simple algorithm for computing (crossing) toroidal Schnyder woods: our approach is based on the vertex shelling paradigm involving canonical orderings<fnref n="3" /> and allows us to get mono-chromatic components which are connected, for at least two of the three colors. Our main result is stated below:

**Theorem 1.** *Given a simple toroidal triangulation $\mathcal{T}$ it is possible to compute in linear time a crossing Schnyder wood of $\mathcal{T}$ such that the mono-chromatic components of color 0 and of color 1 are connected.*

As far as we know, our approach leads to the first implementation for computing toroidal Schnyder woods: previous solutions [17, 22] rely on a very involved case analysis or on unpublished results (requiring more than linear time) and, to our knowledge, they have not been implemented, even in the triangulated case (see Section 1.2 for a more detailed discussion), nor do they provide a guarantee on connectness of any mono-chromatic component.

We also conduct experiments providing an empirical answer to conjectures stated in [17, 1] regarding the existence of Schnyder woods for higher genus surfaces.

<footnote n="1">¹In our pictures we use red for color 0, blue for color 1 and black for color 2.</footnote>

<footnote n="2">²An *i*-cycle, for *i* ∈ {0, 1, 2}, is a mono-chromatic cycle whose edges are of color *i*.</footnote>

<footnote n="3">³In the planar case there exists a linear time algorithm for computing Schnyder woods via canonical orderings [8, 21] performing vertex shellings: the fact that such an algorithm also exists in the toroidal case has been left as an open question in [22].</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: A toroidal simple triangulation of size 9, endowed with three different Schnyder woods.</figcaption></figure>

## 1.2 Related works: computing crossing toroidal Schnyder woods

**Via edge contractions.** One can compute crossing Schnyder woods for essentially 3-connected toroidal maps making use of the approach based on edge contractions [17]. The main idea is to perform a sequence of edge contractions until we are left with few vertices: the Schnyder wood can be recovered by assigning colors after the edge expansions (in reverse order). The validity of this approach relies on a very involved case analysis [17, 22]: this results in a polynomial time algorithm, but it is not known how to get linear time while preserving the crossing condition, which is a non-local property.

**Via three paths meeting at a vertex.** For simple triangulations another way [17] to compute toroidal Schnyder consists in cutting a toroidal triangulation $\mathcal{T}$ along three non-contractible (and non-homotopic) cycles $\Gamma_0, \Gamma_1, \Gamma_2$ whose intersection is a common single vertex $v$. As result one obtains a partition of $\mathcal{T}$ into two quasi-triangulations $G_1$ and $G_2$, which are internally 3-connected and can be endowed with a planar Schnyder wood (refer to [13, 14]). Then computing Schnyder woods for $G_1$ and $G_2$ and gluing them yields a crossing Schnyder wood for $\mathcal{T}$ (see Fig. 2). The Schnyder wood satisfies the following 3-cycles property: there are (at least) three mono-chromatic cycles, one for each color, crossing at a single vertex and which are disjoint elsewhere. It is worth noting that the construction described in [17] does not guarantee that the mono-chromatic components are connected (the Schnyder wood could have several disjoint mono-chromatic $i$-cycles). Unfortunately, as pointed out in [22], it is not clear how to get a linear-time algorithm: the pre-processing phase relies on an unpublished result by Fijavz (the computation of three non-homotopic and non-contractible cycles whose intersection is a common vertex) which involves a result on disjoint paths in [25].

**Via reversal of oriented cycles.** In the triangulated case, the basic approach using edge contraction (without maintaining crossing property) leads to an algorithm for computing balanced toroidal Schnyder woods in linear time (Thm 10 in [22]). As shown in [22] (Thm 11) it is possible to turn a balanced
<figure><img src="image_3.png" /><figcaption>Figure 2: Computing a toroidal Schnyder wood via 3 non-contracting cycles crossing at vertex $v_1$.</figcaption></figure>

Schnyder wood into a half-crossing one by performing the reversal of oriented cycles. Then one can perform another cycle reversal phase in order to make the Schnyder wood crossing (Thm 13 in [22]). All these phases can be executed in linear time, but we are not aware of any existing implementation.<fnref n="4" />

# 2 Preliminaries

## Toroidal and cylindric triangulations.

In this work we deal with toroidal triangulations which are maps on the torus with only triangular faces (such maps are simple if they have no loops nor multiple edges). We will denote by $n$ the total number of vertices. In our drawings we will represent such maps in the planar model of the flat torus. We also consider (simple) cylindric triangulations, which are planar maps with a marked inner face of simple contour denoted $C_{in}$ (the outer face contour being denoted $C_{ext}$) such that all other inner faces have degree 3. $G$ is non-degenerate if $C_{in}$ and $C_{ext}$ are disjoint (not sharing any vertex). We will denote by $n$ the number of vertices of $G \setminus C_{in}$, and will also use notation $\partial^i G$ for $C_{in}$ and $\partial^e G$ for $C_{ext}$. We will draw cylindric triangulations either in the annular representation or in the flat model of the cylinder.

## Toroidal Schnyder woods (for triangulations)

**Definition 2** ([17, 22]). Let $\mathcal{T}$ be a toroidal triangulation. A Schnyder wood of $\mathcal{T}$ is an orientation and labeling, with colors in $\{0, 1, 2\}$ of the edges of $\mathcal{T}$ so as to satisfy the following local Schnyder condition (for all vertices): for each vertex $v$, the edges incident to $v$ in counterclockwise (ccw) order are: one outgoing edge colored 2, zero or more incoming edges colored 1, one outgoing edge colored 0, zero or more incoming edges colored 2, one outgoing edge colored 1, and zero or more incoming edges colored 0.

<footnote n="4">⁴For a fast implementation one needs to efficiently process contractible edges and to maintain the map data structure under local updates: this is not trivial in practice, even in the (planar) triangulated case.</footnote>
A Schnyder wood is half-crossing if there are two distinct colors $i, j \in \{0, 1, 2\}$ such that there is an $i$-cycle crossing a $j$-cycle (in which case all $i$-cycles cross all $j$-cycles). A Schnyder wood is crossing if for each pair of distinct colors $i, j \in \{0, 1, 2\}$ there is an $i$-cycle crossing a $j$-cycle).

The pictures in Fig. 1 show a toroidal triangulation endowed with three Schnyder woods. Definition 2 is particularly elegant since it preserves the symmetry of the three colors, but in general the global spanning property of Schnyder woods is lost: the graph induced by any given color could consist of several disjoint connected components, each component being made of a cycle with trees attached to it (as every vertex has outdegree 1 in a given color).

### Canonical orderings for cylindric triangulations

As shown in [9], it is possible to extend the notion of canonical orderings [18] to the cylindric case as follows. A cylindric canonical ordering is an ordering $\pi = \{v_1, \dots, v_n\}$ of the vertices of $G \setminus C_{in}$ such that, for every $k \ge 0$, the map $G_k$ induced by $C_{in} \cup \{v_1, \dots, v_k\}$ is a cylindric (possibly degenerate) triangulation, and such that, for every $k \ge 1$, the vertex $v_k$ belongs to the outer boundary cycle of $G_k$, denoted $\partial^e G_k$, and its neighbors in $G_{k-1}$ are consecutive boundary vertices on $\partial^e G_{k-1}$. Such an ordering can be computed in linear time via an incremental vertex shelling procedure, where vertices together with their incident edges and faces are removed in reverse order from the boundary $\partial^e G_k$ ($n \ge k \ge 1$). In order to be removed, a vertex $v \in \partial^e G_k \setminus C_{in}$ must be free: $v$ cannot be incident to a chord of $\partial^e G_k$. The existence of free vertices on $\partial^e G_k$ relies on an inductive argument similar to the planar case (we refer to [9] for more details).

## 3 From cylindric Schnyder woods to toroidal Schnyder woods

<figure><img src="image_4.png" /><figcaption>Figure 3: Left: coloring rule associated to the remove operator. Center: local conditions for vertices on $C_{in}$ and $C_{ext}$. Right: a cylindric Schnyder wood of a cylindric triangulation.</figcaption></figure>

For the simple triangulated case, we show how to derive toroidal Schnyder
woods from the notion of cylindric canonical orderings [9]. We first planarize the input triangulation $\mathcal{T}$ cutting along a chordless non contractible cycle $\Gamma$, getting a non-degenerate cylindric triangulation $G$.

<caption>**Algorithm 1:** Computation of a toroidal Schnyder wood via a cylindric canonical ordering</caption>

**Data:** a simple toroidal triangulation $\mathcal{T}$, a non contractible chordless cycle $\Gamma$

**Result:** a toroidal Schnyder wood $S(\mathcal{T})$
cut $\mathcal{T}$ along $\Gamma$: the result is a cylindric triangulation $G$ with boundaries
$C_{in}, C_{ext}$;

$k \leftarrow n$;
$G_k \leftarrow G$, $\partial^e G_k \leftarrow C_{ext}$;

**while** $\partial^e G_k \neq C_{in}$ **do**
| $v \leftarrow$ any free vertex on $\partial^e G_k$;
| remove($v$) from $\partial^e G_k$; /* Orient the edges incident to $v$ in
| $G_k$ */
| $k \leftarrow k - 1$;

**end**
identify edges of $C_{in}$ and $C_{ext}$;

Then we compute a cylindric canonical ordering of $G$ and we proceed as in the planar case by defining a vertex removal operation: at a given shelling step $k$, remove($v$) updates the outer boundary of $G_k$ by removing vertex $v$ while assigning colors and orientations to edges incident to $v$ in $G_k$, as illustrated in the left picture of Fig. 3: the left and right edges ($v, v_{left}$) and ($v, v_{right}$) become outgoing from $v$ (of color 0 and 1), and all remaining edges get oriented toward $v$ (of color 2). This shelling procedure is described in detail in [9], the pseudocode is provided in Algorithm 1. As a result we get a *cylindric Schnyder wood* $S(G)$, i.e., a coloring (in 0, 1 or 2) and an orientation for all edges in $G \setminus C_{in}$ satisfying the three conditions below (depicted in Fig. 3):

• **inner vertices** satisfy the local Schnyder condition as in Definition 2.

• **local condition for $C_{ext}$**: each vertex $v \in C_{ext}$ has exactly two outgoing edges (of color 0 and 1). When traversing the neighbors of $v \in C_{ext}$ in ccw order around $v$ we encounter: a (possibly empty) set of incoming edges (of color 1), an outgoing edge of color 0, a (possibly empty) set of incoming edges (of color 2), an outgoing edge of color 1, and the remaining edges (if any) are incoming of color 0.

• **local condition for $C_{in}$**: each vertex $v \in C_{in}$ has one outgoing incident edge $e$ of color 2; all remaining incident edges are incoming at $v$, being of color 1 if they are at the left of $e$, and of color 0 otherwise.

After identification of the cycles $C_{ext}$ and $C_{in}$ we get back the toroidal
<figure><img src="image_5.png" /><figcaption>Figure 4: Illustration of Algorithm 1. The toroidal triangulation $\mathcal{T}$ is cut along a non-contractible and chordless cycle $\Gamma$. The resulting cylindric triangulation $G$ is endowed with a cylindric canonical ordering (vertices are labeled accordingly), yielding a cylindric Schnyder wood $S(G)$: after gluing $C_{in}$ and $C_{ext}$ we get a toroidal Schnyder wood $S_{\Gamma}(\mathcal{T})$.</figcaption></figure>

triangulation $\mathcal{T}$ endowed with a toroidal Schnyder wood $S_{\Gamma}(\mathcal{T})$ satisfying the additional properties expressed in the Lemma below.

**Lemma 3.** Let $\mathcal{T}$ be a simple toroidal triangulation and $\Gamma$ a chordless non-contractible cycle. The Schnyder woods $S(G)$ and $S_{\Gamma}(\mathcal{T})$ computed as above satisfy (see Fig. 4):

1. in $S(G)$ the edges of color 2 define a spanning forest of $G \setminus C_{ext}$, whose (directed) trees are rooted on a vertex of $C_{ext}$; Similarly, the edges of color 0 (resp. 1) define a spanning forest of $G \setminus C_{in}$, whose (directed) trees are rooted on a vertex of $C_{in}$;

2. in $S_{\Gamma}(\mathcal{T})$ all $i$-cycles cross the cycle $\Gamma$ and are not homotopic to $\Gamma$ (for $i \in \{0, 1, 2\}$);

3. if $S_{\Gamma}(\mathcal{T})$ is half-crossing then the 0-cycles and 1-cycles are pairwise crossing.

*Proof.* We show that the Schnyder woods computed by Algorithm 1 satisfy the properties stated above.
(1) The fact that all vertices on $G \setminus C_{ext}$ get an outgoing edge of color 2 follows from the fact that each $v \in G \setminus C_{ext}$ gets an outgoing edge of color 2 at a given removal step $k$, when $v$ appears for first the time on $\partial^e G_{k-1}$. Moreover, color 2 edges define a forest ending at $C_{ext}$ as shown in [9]. For the remaining colors, it is easy to observe that every vertex $v \in G \setminus C_{in}$ gets an outgoing edge of color 0 and one of color 1 (because of the coloring rule). Note also that for every edge $(u, v)$ of color 0 or 1, the rank of $u$ is larger than the rank of $v$ along the shelling order. This ensures that there is no directed cycle in the graph of color 0 (resp. 1) and that it forms a tree directed toward $C_{in}$.

(2) The Schnyder wood $S_\Gamma(\mathcal{T})$ is obtained after identification of $C_{in}$ and $C_{ext}$. Then (1) ensures that the mono-chromatic components of $S_\Gamma(\mathcal{T})$ cannot contain mono-chromatic $i$-cycles which are parallel to $\Gamma$ and do not cross $\Gamma$ (otherwise we would have a cycle homotopic to $C_{ext}$ in the cylindric Schnyder wood $S(G)$). On the other hand, mono-chromatic $i$-cycles can not even cross $\Gamma$ while being homotopic to $\Gamma$. Indeed, any $i$-cycle in $S_\Gamma(\mathcal{T})$ is non-contractible and oriented (refer to [17]), and if it crosses $\Gamma$ we would find a vertex $v \in C_{in}$ having an outgoing incident edge of color $i$ (for $i = 0, 1$) in the cylindric Schnyder wood $S(G)$, thus contradicting the conditions stated in Section 3. A similar argument holds for mono-chromatic cycles of color 2.

(3) As already mentioned, the toroidal Schnyder woods computed in Section 3 via cylindric canonical orderings are not necessarily crossing or half-crossing. Nevertheless, let us show that if such a toroidal Schnyder wood $S_\Gamma(\mathcal{T})$ is half-crossing, then the 0-cycles must cross the 1-cycles.

Assume for contradiction that there exist a 0-cycle $C_0$ and a 1-cycle $C_1$ which are parallel: then they must each cross the 2-cycles (otherwise $S_\Gamma(\mathcal{T})$ would not be half-crossing). We distinguish two cases depending on the orientations of $C_0$ and $C_1$.

If $C_0$ and $C_1$ are oriented in the same direction, then they cross any 2-cycle from the same side at two vertices $w$ and $z$: this cannot occur since we would find a vertex (either $w$ or $z$) where the local Schnyder condition is violated.

So it remains to consider when $C_0$ and $C_1$ are parallel and oriented in opposite direction. Because of the previous properties, we know that both $C_0$ and $C_1$ must cross the cycle $\Gamma$. And since $C_0$ and $C_1$ are in opposite directions, there must exist two edges $e_0 \in C_0$ and $e_1 \in C_1$ each starting at a vertex on $\Gamma$, and leaving $\Gamma$ in opposite sides (one on the left side of $\Gamma$ and the other on the right side of $\Gamma$). Hence, in the cylindric Schnyder wood associated to $S_\Gamma(\mathcal{T})$, at least one edge (either $e_0$ or $e_1$) is outgoing from $C_{in}$ and not of color 2, violating the local conditions at $C_{in}$ described in Section 3, which leads to a contradiction. $\square$

## Balanced Schnyder woods

As illustrated in Fig. 4 the Schnyder woods computed by Algorithm 1 may fail to be crossing or half-crossing (we will remedy this in the next sections), but as we
show here they satisfy the important property of being balanced. A Schnyder wood is called balanced if every non-contractible (undirected) cycle C has the same number of outgoing edges on each side. It is actually sufficient (Lemma 34 in [22]) to have the condition satisfied by two non-contractible cycles that are not homotopic.

**Corollary 4.** *The Schnyder woods computed by Algorithm 1 are balanced.*

*Proof.* Let us consider the pair of cycles $(\Gamma, C_2)$, where $\Gamma$ is the non-contractible cycle used to cut the triangulation and $C_2$ is any 2-cycle in the Schnyder wood. Observe that $\Gamma$ and $C_2$ are non-homotopic because of property (2) stated in Lemma 3.

The cycle $C_2$ is mono-chromatic (and directed) and has the same number of outgoing edges leaving it at the left and at the right because of the local Schnyder condition. The cycle $\Gamma$ (whose size is denoted $n_{\Gamma}$) is undirected and consists of edges of color 0 or 1. Because of property (1) stated in Lemma 3, $\Gamma$ has on one of its sides only outgoing edges of color 2: there are $n_{\Gamma}$ such edges, as every vertex has exactly one outgoing edge for each color. On the other side $\Gamma$ has also $n_{\Gamma}$ outgoing edges (of color either 0 or 1): since every vertex on $\Gamma$ has two outgoing edges (of color 0 and 1) and the total number of edges on $\Gamma$ is $n_{\Gamma}$, then there are exactly $n_{\Gamma}$ outgoing edges of color 0 or 1 which are not on $\Gamma$, and leaving it on the same side, because of (2) in Lemma 3. Which shows that the Schnyder wood is balanced. $\square$

Balanced Schnyder woods are very instrumental in the bijective encoding [11, 16] of simple toroidal triangulations by decorated unicellular maps (which yields an asymptotically optimal encoding procedure). Indeed the first step of the construction is to compute the so-called minimal balanced Schnyder wood of the simple toroidal triangulation $\mathcal{T}$ to be encoded. It turns out that this can easily be done in linear time (by an adaptation of the planar-case arguments given in [7], see also [19, Lemma 3.2]) starting from an arbitrary balanced Schnyder wood of $\mathcal{T}$, as provided by Algorithm 1.

## 3.1 $P$-constrained cylindric Schnyder woods

Assume we are given a cylindric triangulation $G$ with two boundary cycles $C_{in}$ and $C_{ext}$ (with no chord at $C_{in}$) and a chordless path $P = \{u_0, u_1, \dots, u_{t-1}\}$ originating from vertex $u_0 \in C_{in}$ and ending at $u_{t-1} \in C_{ext}$, such that $P$ intersects the boundary cycles of $G$ only at $u_0$ and $u_{t-1}$. We explain here how to adapt the shelling procedure so as to obtain a cylindric Schnyder wood of $G$ such that $P$ is a directed path in color 2.

**Definition 5.** Let $P = \{u_0, u_1, \dots, u_{t-1}\}$ be a path satisfying the conditions above. A cylindric Schnyder wood of $G$ is called $P$-constrained if every edge $(u_i, u_{i+1}) \in P$ is oriented toward $u_{i+1}$ and has color 2.

We say that a boundary vertex $v \in \partial^e G_k \setminus P$ (for $k \ge 1$) is strongly free (with respect to $P$) if $v$ is free and not adjacent to any vertex of $P_k$, where
<figure><img src="image_6.png" /><figcaption>Figure 5: Computation of a P-constrained Schnyder wood (Lemma 6): only vertices which are strongly free (with respect to the path $P = \{u_0, \dots, u_{t-1}\}$) can be removed at each step.</figcaption></figure>

$P_k = P \cap (G_k \setminus \partial^e G_k)$ is the restriction of $P$ to the interior of $G_k$. The vertex $u \in P \cap \partial^e G_k$ is strongly free if it does not have any incident chord at $\partial^e G_k$. We modify the shelling procedure described in the previous section by removing at each shelling step only vertices on $\partial^e G_k$ which are strongly free, as illustrated in Fig. 5.

**Lemma 6.** *Given a cylindric triangulation G and a path P defined as above, the adapted shelling procedure outputs a P-constrained Schnyder wood of G, and runs in linear time.*

*Proof.* Let us first show that the modified shelling procedure terminates. It is easily seen that at each shelling step there is at least one vertex on $\partial^e G_k$ which is strongly free (with respect to $P$) and that can thus be removed. Indeed, if $u \in P \cap \partial^e G_k$ has no incident chords at $\partial^e G_k$ then it is strongly free by definition. Otherwise such a vertex $u$ is incident to a chord $e = (u, v)$ (with $v \in \partial^e G_k$): in this case the planar region above the chordal edge $e$ contains at least one vertex $z \in \partial^e G_k$ which is free (by an inductive argument as in [9]). Such a vertex $z$ cannot be adjacent to any inner vertex of $P_k$ (otherwise one could find a crossing between $e$ and an edge emanating from a vertex in $P_k$), which guarantees that $z$ is strongly free.

For the correctness, observe that shelling strongly free vertices maintains the property that $P$ intersects $\partial^e G_k$ at a single vertex. This ensures that the edges of $P$ get color 2 (to be of color 0 or 1 would mean that the edge is on $\partial^e G_k$ at some step), and that $P$ is directed from $C_{in}$ to $C_{ext}$.

<figure><img src="image_7.png" /></figure>
# 4 Rivers

<figure><img src="image_8.png" /><figcaption>Figure 6: (Left) annular representation of a river R with a chordless path P crossing only once its boundary cycles. Right: only non-trivial chords are drawn, as dotted arcs.</figcaption></figure>

We consider here a particular type of “thin” cylindric triangulations called *rivers*, for which we compute a so-called *rigthmost* (resp. *leftmost*) *P*-constrained Schnyder wood. Rivers, and properties of their rightmost (resp. leftmost) Schnyder wood, are key to obtain the half-crossing (resp. crossing) property, as presented in Section 5 (resp. Section 6).

## 4.1 Definition of a river

Let us define a river R as a non-degenerate simple cylindric triangulation whose outer and inner boundary cycles, denoted $\partial^i R = \{x_0, x_1, \dots, x_{r-1}\}$ and $\partial^e R = \{z_0, z_1, z_2, \dots, z_{s-1}\}$, satisfy the following conditions: $\partial^i R$ and $\partial^e R$ are chordless cycles such that every vertex $z \in \partial^e R$ has an incident edge $(z, \bar{x})$, where $\bar{x} \in \partial^i R$, and every vertex $x \in \partial^i R$ has an incident edge $(x, \bar{z})$, where $\bar{z} \in \partial^e R$ (such edges are called *non-trivial chords* of R).

## 4.2 Right-most (left-most) cylindric canonical ordering of a river

Let us assume that R is provided with a chordless path $P = \{u_0, \dots, u_{t-1}\}$ intersecting its boundaries only once, at $u_0 = x_0$ and $u_{t-1} = z_0$ (refer to Fig. 6). Observe that the non-trivial chords $(u, y)$, where $u$ is either $u_0$ or $u_{t-1}$ and $y \in (\partial^i R \cup \partial^e R) \setminus P$, can be partitioned into two (possibly empty) sets, depending on whether $(u, y)$ is at the right or at the left of the path $P$. We classify the vertex $u_{t-1}$ according to four types (see Fig. 7):

(A): $u_{t-1}$ has chords both at the left and at the right of P;

(B): $u_{t-1}$ has no chords at the left nor at the right of P, so that $(u_0, u_{t-1})$ is the only chord at $u_{t-1}$;

(C1): $u_{t-1}$ has chords at the right of P, but not at the left of P;
(C2): $u_{t-1}$ has chords at the left of $P$, but not at the right of $P$.

Let us now define the right-most traversal of $R$ with respect to $P$ (yielding a $P$-constrained cylindric Schnyder wood) as given by Algorithm 2 below (refer also to Fig. 7 for an illustration):

<caption>**Algorithm 2:** Right-most traversal of a river</caption>

**Data:** a river $R$, a path $P = \{u_0, u_1, \dots, u_{t-1} = z_0\}$
**Result:** a $P$-constrained cylindric Schnyder wood of $R$
**if** $u_{t-1}$ is of type (A) then
| $v \leftarrow z_1$;
**else**
| $v \leftarrow z_0$;
**end**
$x_c \leftarrow$ extremity of the left-most chord of $v$;
remove $v$ from the outer boundary $\partial^e R$;
**while** $\partial^e R \neq \partial^i R$ do
| $v \leftarrow$ the strongly free vertex on $\partial^e R$ which is closest to $x_c$ at its
| right;
| remove $v$ from the outer boundary $\partial^e R$;
**end**

One crucial property is that, after computing a $P$-constrained Schnyder wood $S_P(R)$ according to a right-most traversal, if $u_{t-1}$ is of type (A), (B) or (C1) then every vertex $z$ on $\partial^e R$ lies on a path of color 1 ending at $P$. If $u_{t-1}$ is of type (C2) this property may fail, but the right-most traversal leads to the existence of a ccw-oriented contractible cycle enclosed in $R$. These properties are a consequence of the statement below.

**Lemma 7.** Let us consider a river $R$ and a chordless path $P$ as defined above. Let $S_P(R)$ be the $P$-constrained cylindric Schnyder wood computed by Algorithm 2. Then we have:

1. if $u_{t-1}$ is of type (A), then for every vertex $z_i \in \partial^e R$ with $1 < i < s$, the path of color 1 starting from $z_i$ passes by $u_{t-1}$;

2. if $u_{t-1}$ is of type (B) or (C1), then for every vertex $z \in \partial^e R$, the path of color 1 starting from $z$ ends at $u_0$;

3. if $u_{t-1}$ is of type (C2): then all vertices $z_i$ are lying on a path of color 1 ending either at $P$ or at $x_c$. Moreover, there exists at least one vertex $z_i$ lying on a ccw-oriented cycle (enclosed in $R$) defined by $(x_c, u_{t-1}, z_{s-1}, \dots, z_i)$.

*Proof.* First observe that if case (A) occurs then $P$ (which is chordless) consists of a single edge $(u_0, u_1)$. Indeed, the presence of chords at $u_{t-1}$ on both sides of $P$ implies that $u_{t-1}$ is the only vertex of $\partial^e R$ that can be adjacent to $u_0$ (an edge from $u_0$ to any other vertex of $\partial^e R$ would have to cross a chord). A similar argument applies when case (B) occurs: again the path $P$ is of length one.
<figure><img src="image_9.png" /><figcaption>Figure 7: Illustration of Algorithm 2 and Lemma 7: we distinguish four cases for the right-most traversal of a river $R$. Left pictures: removal of the first vertex on $\partial^e R$. Center pictures: paths of color 1 obtained via a right-most traversal of $R$. Right pictures: complete execution of Algorithm 2 on four examples (vertex labels are assigned according to the cylindric canonical ordering).</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 8: Case analysis of the proof of Lemma 7.</figcaption></figure>

If case (C1) occurs then $u_0$ must have at least one non-trivial chord at the left of $P$: observe that $u_0$ has at least one incident non-trivial chord (since it is on the boundary cycle of a river) and cannot have chords at the right of $P$ (such non-trivial chords would cross one of the chords ($u_{t-1}, x$) at the right of $P$, contradicting the planarity of $R$). A similar (symmetric) argument applies when case (C2) occurs, when there are no non-trivial chords ($u_{t-1}, x$) at the right of $P$: in this case there must be some non-trivial chords ($u_0, z$) at the right of $P$.

**Claim: algorithm 2 terminates and computes a P-constrained Schnyder wood.** At the first step we remove either $u_{t-1}$ (cases B, C1 and C2) or $z_1$ (case A). In cases (B, C1, C2), we know that $u_{t-1}$ is always strongly free since the path $P$ is assumed to be chordless. In case (A), vertex $z_1$ must also be strongly free, otherwise an edge ($z_1, u$) (with $u \in P$) would cross the non-trivial chords incident to $u_{t-1}$. After the first vertex removal of $v$, we simply apply the vertex shelling process to the cylindric degenerate triangulation $R \setminus v$ (which is guaranteed to terminate).

Observe that the resulting Schnyder wood is P-constrained. If cases (B) or (C1, C2) occur then just apply the arguments of Claim 6 to $R \setminus v$. If case (A) occurs then $P = (u_0, u_1)$ must be of color 2 and oriented toward $u_1$, since there are non-trivial chords incident at $u_1$ both at the left and at the right of $P$ (because of the Schnyder local condition at $u_{t-1}$).

We distinguish several cases (depicted in Fig. 8).

**Case 1, vertex of type (A):** Let us prove that there exists a path of color 1 starting at $z_i$ and passing through $u_{t-1}$: without loss of generality, assume that the outgoing edge of color 1 at $z_i$ is not lying on $\partial^e R$ (otherwise, repeat the same argument with the right neighbor of $z_i$ on $\partial^e R$).

Let us denote by $Q_1(z_i)$ the path originating from $z_i$ obtained following the outgoing edges of color 1 and assume by contradiction that this path does not reach $u_{t-1}$. Because of Lemma 3 this path must end at $\partial^i R$, so $Q_1(z_i) = \{z_i, w_1, w_2, \dots, \bar{x}\}$, where $\bar{x} \neq x_0$ since there are chords incident to $u_{t-1}$ (on both sides).

Let us consider the path $Q_2(\bar{x})$ of color 2 starting at $\bar{x}$ and ending at some vertex $\bar{z} \in \partial^e R$. Observe that $\bar{z}$ is a boundary vertex following $z_i$ on $\partial^e R$ ($\bar{z}$ is
possibly coinciding with $u_{t-1}$), since the outgoing edge of color 2 at $\bar{x}$ follows in cw direction the incoming edge of color 1 of path $Q_1(z_i)$. Then consider the outgoing edge of color 0 at $\bar{z}$: this edge is the starting point of a third path $Q_0(\bar{z})$ of color 0 ending at $\partial^i R$. Observe that $Q_0(\bar{z})$ cannot reach $\bar{x}$, otherwise the local Schnyder condition at $\bar{x}$ would be violated: so it must intersect $Q_1(z_i)$ at a vertex $\bar{w}$. It turns out that $\bar{w}$ must coincide with $z_i$: otherwise the path $Q_0$ and $Q_1$ would enclose a portion of $\partial^e R$ containing at least one vertex $z_j$ (with $j > i$) without non trivial chords, which contradicts the fact that $R$ is a river.

So, we have found a ccw-oriented cycle defined by the concatenation of $Q_1(z_i)$, $Q_2(\bar{x})$ and $Q_0(\bar{z})$, bounding a planar region (shaded region in Fig. 8). This implies that $\pi(\bar{z}) > \pi(z_i)$ and so $\bar{z}$ has been removed before $z_i$ during the right-most traversal of $R$: this can occur only if $z_i$ has some incident chords which make it not strongly free. But $z_i$ cannot be neighbor of a vertex (different from $u_{t-1}$) on $P$: otherwise we would have an edge crossing some chords at $u_{t-1}$. Moreover, there are no chords $(z_i, z_k)$ (where $z_k$ is at the right of $\bar{z}$): such chords would cross the path $Q_2(\bar{x})$. So, $z_i$ can be removed before $\bar{z}$ during the right-most traversal of $R$, which contradicts that $\pi(\bar{z}) > \pi(z_i)$ and the existence of the ccw-oriented path defined above.

**Case 2, vertex of type (B) or (C1):** First observe that any non trivial chord $(\bar{z}, u_0)$ must be oriented toward $u_0$ (of color 1) because of the local Schnyder condition at $u_0$. For any other vertex $z_i$ (not neighbor of $u_0$) we can proceed in a similar way as for case A. Assume that there is a path of color 1 starting at $z_i$ not reaching $u_0$: then such path, denoted $Q_1$, must reach $\partial^i R$ at a vertex $\bar{x}$ (different from $u_0$).

An argument similar to the one of case (A) shows the existence of a ccw-oriented contractible cycle $C$, obtained via the concatenation of three paths $Q_1$, $Q_2(\bar{x})$ and $Q_0$. More precisely, the existence of a path $Q_0$ of color 0 reaching $z_i$ implies that $z_i$ has been removed after a vertex $\bar{z}$ on its right during the right-most traversal of $R$. This contradicts the fact that $z_i$ is strongly free: the non trivial chords at $u_0$ would be prevented if any edge $(z_i, u)$ (with $u \neq u_0$).

**Case 3, vertex of type (C2): if there is no non-trivial chord $(z_i, x_j)$ (with $x_j \neq u_0$) of color 1 then $R$ contains a ccw-oriented cycle.** Observe that if the right-most traversal of $R$ leads to the existence of a chord $(z_i, x_j)$ of color 1 (this can only occur in case (C2)), we can find a ccw-oriented cycle starting at $x_j$ and following the outgoing edge of color 2 which is a chord $(x_c, u_{t-1})$. Then, following the path of color 0 on $\partial^e R$ starting from $u_{t-1}$ we reach vertex $z_i$ (the last edge is of color 1 oriented toward $x_j$), which concludes the proof. $\square$

**Left-most traversal.**

One can define left-most traversals proceeding in a symmetric way with respect to Algorithm 2: at the beginning we set $v = z_{s-1}$ if $u_{t-1}$ is of type (A) and $v = z_0$
otherwise; $x_c$ is set to be the extremity of the right-most chord of $v$; finally, at each shelling step one removes the strongly free vertex which is closest at the left of $x_c$.

Similarly to the properties stated in Lemma 7 one can show that if $u_{t-1}$ is of type (A), (B) or (C2) then each vertex $z$ on $\partial^e R$ lies on a path of color 0 ending at $P$.

# 5 Algorithm for half-crossing toroidal Schnyder woods

We describe in this section an algorithm to compute a half-crossing toroidal Schnyder wood for any simple toroidal triangulation, with the further property that the mono-chromatic component in color 0 or in color 1 is connected.

## 5.1 Existence of a river in cylindric triangulations

A key ingredient of the algorithm is the computation of a river in the cylindric triangulation that is obtained by cutting along a chordless non-contractible cycle.

**Lemma 8.** *Given a non-degenerate cylindric triangulation $G$ with no chord at $C_{in}$ or $C_{ext}$, it is possible to compute in linear time a river $R$ contained in $G$, whose inner and outer boundaries are homotopic to $\partial^i G$.*

*Proof.* We mark all vertices that are at distance 1 from the inner cycle $C_{in}$ of $G$. Then we perform a vertex shelling of $G$ (as the one corresponding to a canonical ordering), removing only free vertices that are not marked. At the end of this process we are left with a cylindric triangulation $G'$ whose outer boundary $\partial^e G'$ is chordless and such that all its vertices are at distance one from $C_{in}$ (observe that if there would be a chord on $\partial^e G$ then we could find a vertex $v \in \partial^e G$ which is free and at distance more than 1 from $C_{in}$, and it could be removed from $G'$ with a further shelling step).

It now remains to remove all vertices on $\partial^i G' = C_{in}$ which are at distance more than 1 from $\partial^e G'$: this can be obtained by performing a vertex shelling in a symmetric way (from bottom to top), starting to remove vertices from $C_{in}$ (the role of $\partial^i G'$ and $\partial^e G'$ are exchanged). The resulting cylindric triangulation $G''$ is a river (whose inner cycle has a non empty intersection with $C_{in}$).

Overall the computation of $R$ takes linear time, as it requires two passes of a vertex shelling procedure. $\square$

## 5.2 Algorithm

Let $\mathcal{T}$ be a simple toroidal triangulation. We now describe the algorithm computing a half-crossing Schnyder woods of $\mathcal{T}$; the complete pseudo-code is provided in Algorithm 3, see also Figure 9 for an illustration on an example. After cutting $\mathcal{T}$ along a non-contractible and chordless cycle $\Gamma$ (as in Section 3), we
obtain a non-degenerate cylindric triangulation $G$, and compute a river $R$ in $G$ (Lemma 8). As a result, the faces of $G$ are partitioned into three regions: $G_{top}$ (a possibly degenerate cylindric triangulation), the river $R$, and $G_{bottom}$ (a possibly degenerate cylindric triangulation).

The algorithm relies on two passes (the second one not always necessary). In the first pass, we let $P$ be an arbitrary non-trivial chordal edge $\{x, z\}$ for the river $R$. If $z$ is not of type C2, we perform a rightmost traversal of $R$, otherwise a leftmost traversal. We also compute in an independent way two (arbitrary) Schnyder woods of $G_{top}$ and $G_{bottom}$: after boundary identifications we obtain a Schnyder wood $S(T)$ of $T$. It follows from Lemma 7 (see the proof of Proposition 9) that if $z$ is not (resp. is) of type C2, then there is a single monochromatic cycle $C$ of color 1 (resp. color 0), and moreover it winds only once around $\Gamma$ (it may share edges with $\Gamma$ but reaches it only once from the left). If $C$ crosses any cycle of color 2, then we output $S(T)$. Otherwise we need a second pass. Let $\gamma_2$ be an arbitrary 2-cycle. Note that $\gamma_2$ winds once around $\Gamma$ since it is homotopic to $C$. Due to edge colors and local Schnyder conditions, it intersects $\gamma_2$ at a single vertex (as opposed to $C$ it can not share edges with $\Gamma$). Hence, if we cut $\gamma_2$ along $\Gamma$, we obtain a path $P_2 \subset G$ which is chordless and meets the boundary cycles only at its extremities. We can then adjust the Schnyder wood in $R$ as follows: if the upper end of $P_2$ is not of type C2, we perform a rightmost traversal of $R$ with respect to $P_2$, otherwise a leftmost traversal. This updates $S(T)$ into a half-crossing Schnyder wood, such that in the first (resp. second) case there is a single cycle of color 1 (resp. 0) and it the cycle $\gamma_2$ of color 2.

**Proposition 9.** Given a simple toroidal triangulation $T$, Algorithm 3 computes in linear time a half-crossing Schnyder wood of $T$ via vertex shellings. More precisely, there is $r \in \{0, 1\}$ such that the edges of color $r$ define a single connected component, and the unique $r$-cycle crosses the 2-cycles.

*Proof.* Without loss of generality assume that the river $R$ has been traversed in a right-most manner (running Algorithm 2), so that $r = 1$.

**Claim 1: the mono-chromatic component of color $r$ crosses $\Gamma$ only once.** Assume for contradiction that there exists an $r$-cycle crossing $\Gamma$ more than once: after cutting $T$ along $\Gamma$ this cycle leads to disjoint and parallel paths in $G$. Let us consider two such parallel paths $Q$ and $Q'$ of color $r$ in $G$, intersecting the boundary cycles of the river $R$ in distinct vertices $a, a' \in \partial^e R$ and $b, b' \in \partial^i R$ respectively.

If type (A) occurs, consider the restriction of paths $Q$ and $Q'$ to $R$: these two paths start at $a$ and $a'$ respectively and cross $P$ at $u_{t-1}$ because of Lemma 7 (so $Q$ and $Q'$ are not parallel). Similarly, if type (B) or (C1) occurs, then $Q$ and $Q'$ cross the boundary $\partial^i R$ at the same vertex $u_0 \in P$, again because of the properties of Lemma 7. If case (C2) occurs, we proceed in a similar and symmetric manner: the river is traversed in a left-most manner, and the color of the mono-chromatic component is $r = 0$. The same argument as above applies (taking the mirror would amount to be in case (C1)).
**Algorithm 3:** Half-crossing Schnyder woods (with a connected monochromatic component)

**Data:** a simple toroidal triangulation $\mathcal{T}$, a non-contractible chordless cycle $\Gamma$

**Result:** a half-crossing Schnyder wood

// Pre-processing step

cut $\mathcal{T}$ along $\Gamma$: let $G$ be the resulting cylindric triangulation;
compute a river $R$ and the partition $G = G_{top} \cup R \cup G_{bottom}$;
// First pass

compute a Schnyder wood $S(G_{top})$ of $G_{top}$;
choose an arbitrary non trivial chord $e = (x, z)$ of $R$;
$P \leftarrow \{x, z\}$;

if $z$ has type (A), (B) or (C1) then

| run the right-most $P$-constrained traversal of $(R, P)$;
  $r \leftarrow 1$;

else

| run the left-most $P$-constrained traversal of $(R, P)$;
  $r \leftarrow 0$;

end

compute a Schnyder wood $S(G_{bottom})$ of $G_{bottom}$;
glue boundary cycles together and let

$$S(\mathcal{T}) = S(G_{bottom}) \cup S(R) \cup S(G_{top});$$

if the $r$-cycle and 2-cycles are crossing in $S(\mathcal{T})$ then
| return $S(\mathcal{T})$;

end

// Run a second pass on $R$

$\gamma_2 \leftarrow$ any 2-cycle of $S(\mathcal{T})$; // Remark: the $r$-cycle and 2-cycles are parallel

$P_2 \leftarrow \gamma_2 \cap R$; // restriction of $\gamma_2$ to the river $R$

$u \leftarrow \partial^e R \cap P_2$;

if $u$ has type (A), (B) or (C1) then
| run the right-most $P$-constrained traversal of $(R, P_2)$;
  $r \leftarrow 1$;

else

| run the left-most $P$-constrained traversal of $(R, P_2)$;
  $r \leftarrow 0$;

end

// Remark: $S(G_{bottom})$ and $S(G_{top})$ are $P_2$-constrained

glue boundary cycles together and let

$$S(\mathcal{T}) = S(G_{bottom}) \cup S(R) \cup S(G_{top});$$

return $S(\mathcal{T})$;
<figure><img src="image_11.png" /><figcaption>Figure 9: Execution of Algorithm 3 on a small example.</figcaption></figure>
**Claim 2:** the *r*-cycle of the mono-chromatic component of color *r* crosses the 2-cycles. If Algorithm 3 terminates after the first pass, then we are done (the Schnyder wood is half-crossing). Otherwise, the algorithm terminates after performing the second pass: this means that at the end of the first pass the 2-cycles are parallel to the *r*-cycles. Claim 1 ensures that any *r*-cycle $C_r$ crosses $\Gamma$ only once. Hence the same holds for any 2-cycle $\gamma_2$.

Let us consider such a cycle $\gamma_2$ and its restriction to $G$ (obtained after cutting $\mathcal{T}$ along $\Gamma$): this is a path $P_2$ of color 2. A first observation is that $P_2$ is chordless. Indeed, there are no chords whose extremities are both on the same side of $P_2$ (either on the right or on the left), otherwise we could find a vertex on $P_2$ violating the local Schnyder wood condition. And neither are there chords starting on the right side and ending at the left side of $P_2$ (and viceversa), since such a chord (starting at $P_2$) would have to cross $C_r$ before reaching $P_2$ on the other side. So the path $P_2$ satisfies the assumptions of Lemma 6 and we can perform a right-most (or left-most) traversal of the river $R$ (with respect to $P_2$).

To conclude, observe that the restriction of every *r*-cycle to $R$ intersects $P_2 = \gamma_2 \cap R$ (because of Lemma 7): this implies that any *r*-cycle crosses $\gamma_2$ in $\mathcal{T}$.

So the $P_2$-constrained Schnyder wood computed at the end of the second pass is half-crossing: every *r*-cycle crosses every 2-cycle.

**Claim 3:** the edges of color *r* define a single connected component. Assume for contradiction there are two *r*-cycles (which must be parallel and lying in distinct components). Their restrictions in $G$ (after cutting along $\mathcal{T}$) would lead to two parallel paths $Q$ and $Q'$. Applying the same argument as in Claim 1 yields a contradiction. $\square$

# 6 Algorithm for crossing toroidal Schnyder woods

Building on the ideas of Section 5, we give in this section a linear-time algorithm for computing a crossing toroidal Schnyder wood, with the additional property that the mono-chromatic components in color 0 and in color 1 are connected, as stated in Theorem 1.

## 6.1 Existence of two non-overlapping rivers in cylindric triangulations

Compared to the procedure for half-crossing Schnyder woods, the algorithm for crossing Schnyder woods now requires the computation of two parallel and non-overlapping rivers $R_t$ and $R_b$ in the cylindric triangulation obtained after cutting along a non-contractible and chordless cycle. The existence of such a pair of rivers is guaranteed by the next statement.

**Lemma 10.** Given a non-degenerate cylindric triangulation $G$ with no chord at $C_{in}$ or $C_{ext}$, nor between $C_{in}$ and $C_{ext}$, it is possible in linear time to compute a pair of non-overlapping rivers $R_t$ (top river) and $R_b$ (bottom river) contained in $G$, whose inner and outer boundaries are homotopic to $\partial^1 G$.
<figure><img src="image_12.png" /><figcaption>Figure 10: Illustration of the algorithm of Section 6.2 for computing crossing Schnyder woods. At the end of the first phase the Schnyder wood is half-crossing but not crossing (the 1-cycle is parallel to the 2-cycles). But the bottom river contains a ccw-oriented contractible cycle *C* (enclosing the shaded green region): the reversal of *C* leads to a 1-cycle parallel to Γ and thus crossing the 2-cycles, making the Schnyder wood crossing. The edges of color 0 and 1 define a connected component.</figcaption></figure>

*Proof.* We apply the decomposition in the proof of Lemma 8: let $R_b$ be the obtained river, and let $G_{top}$ be the cylindric triangulation above $R_b$. Since all vertices of $\partial^e R_b$ are at distance 1 from $C_{in}$, and since there is no chord between $C_{in}$ and $C_{ext}$, the triangulation $G_{top}$ is non-degenerate, so we can apply the procedure of Lemma 8 to $G_{top}$, yielding a second river $R_t$ (note that $\partial^e R_b$ and $\partial^i R_t$ may share vertices and edges, but their interiors are disjoint). Overall the computation of $R_t$ and $R_b$ requires linear time, since each river requires two passes of a vertex shelling procedure. $\square$

## 6.2 Algorithm

Given a toroidal simple triangulation $\mathcal{T}$, as before the first step consists in cutting $\mathcal{T}$ along a chordless non-contractible cycle $\Gamma$, yielding a cylindric triangulation $G$. Since $\Gamma$ is chordless, the triangulation $G$ has no chord at $C_{in}$ or at $C_{ext}$, nor chords from $C_{in}$ to $C_{ext}$ (such an edge would correspond to a chord of $\Gamma$ starting at one side and ending at the other side). Hence we can apply Lemma 10, which yields a decomposition of $G$ into five components (from top to bottom): a top cylindric triangulation $G_{top}$, the river $R_t$, a middle cylindric triangulation $G_{middle}$, the river $R_b$, and a bottom cylindric triangulation $G_{bottom}$. Note that $G_{top}$, $G_{middle}$ and $G_{bottom}$ are possibly degenerate. We then follow the pipeline used in Algorithm 3: one river (resp. the other river) is used to guarantee that color 0 (resp. color 1) is crossing color 2, and that the mono-chromatic component is connected.

Precisely, in a first pass, we choose a chord $e_t$ in $R_t$ that is the leftmost chord at its top vertex, and let $P_t = e_t$ be the path according to which we perform a rightmost traversal of $R_t$ (note that $(R_t, P_t)$ is of type B or $C_1$). Similarly, we choose a chord $e_b$ in $R_b$ that is the rightmost chord at its top vertex, and we let $P_b = e_b$ be the path according to which we perform a leftmost traversal of $R_b$.
(note that $(R_b, P_b)$ is of type B or $C_2$). We also compute an arbitrary cylindric Schnyder wood for each of the three components $G_{top}$, $G_{middle}$, and $G_{bottom}$. Then we glue together the Schnyder woods for the five components. Identifying $C_{in}$ with $C_{ext}$ we obtain a toroidal Schnyder wood of $\mathcal{T}$. From Lemma 7 and arguments already used in Section 5, the mono-chromatic component of color 1 (resp. color 0) is connected, thanks to the top-river (resp. bottom river). If the Schnyder wood is crossing we return it as the output.

If it is not crossing we need a second pass, similarly to Section 5. By the 3rd item in Lemma 3 we must have either color 1 parallel to color 2, or color 0 parallel to color 2. In both cases, due to the rivers, the non-contractible cycles of color 2 must wind only once (they cross $\Gamma$ at a single vertex), so in $G$ such a cycle $\gamma_2$ gives a path $P_2$ from $C_{in}$ to $C_{ext}$. Keeping the Schnyder woods for $G_{top}$, $G_{middle}$, and $G_{bottom}$ unchanged, we need a second pass to adjust those for $R_t$ and $R_b$ in order to obtain the crossing property. Precisely, let $P_t$ (resp. $P_b$) be the restriction of $P_2$ to $R_t$ (resp. $R_b$). If $(R_t, P_t)$ and $(R_b, P_b)$ are not both of type C2 or are not both of type C1, then we can choose one of them, denote it by $(R', P')$, not to be of type C2, and the other one, denote it by $(R'', P'')$, not to be of type C1. Then we perform a right-most traversal for $(R', P')$, and a left-most traversal for $(R'', P'')$. After these updates on the Schnyder woods for the two rivers, and by the arguments of Section 5, the toroidal Schnyder wood of $\mathcal{T}$ now has the property that cycles of color 1 (resp. 0) cross cycles of color 2 thanks to $R'$ (resp. $R''$), and that the monochromatic component of color 1 (resp. 0) are still connected.

It remains to treat the case where at the second pass we have $(R_t, P_t)$ and $(R_b, P_b)$ both of type C1 or both of type C2. Let us assume they are both of type C2. Then we adjust the Schnyder woods in $R_t$ and $R_b$ by performing the leftmost $P_t$-constrained traversal of $R_t$, and the rightmost $P_b$-constrained traversal of $R_b$. At this point we have the crossing of color 0 with color 2, thanks to the top river and the 2nd item in Lemma 3. In color 1 the crossing property may however fail. But we can take advantage of the 3rd item in Lemma 7, which guarantees the existence of a specific directed cycle $C$ in $R_b$. Reversing this cycle makes $\partial^e R_b$ a cycle in color 1 that is parallel to $\Gamma$.

**Claim 11.** If in the second phase the rivers $(R_t, P_t)$ and $(R_b, P_b)$ are of type C2, then after reversing the cycle $C$, the toroidal Schnyder wood of $\mathcal{T}$ is crossing, and the mono-chromatic components of color 0 and of color 1 are connected.

*Proof.* Recall that the cycle $C$ is made of a subpath $Q = z_i, \dots, z_{s-1}, u_{t-1}$ of $\partial^e R_b$, together with a single vertex $x_c \neq u_0$ on $\partial^i R_b$ (bottom vertex of $C$). Regarding the properties in color 0 (prove that it has a single cycle crossing the cycles of color 2), we just need to check that reversing $^5C$ does not affect the fact ($F_0$) that for every vertex $v$ of the cylindric triangulation $G$, the path of color 0 starting from $v$ still ends at $C_{in}$. Note that the only vertices whose

<footnote>$^5$Observe that reversing an oriented contractible cycle yields a new orientation which admits a re-coloring of the inner edges (inside the region bounded by the cycle) fullfilling the requirements of a Schnyder wood.</footnote>
outgoing edge of color 0 has changed are those of $Q\setminus z_i$ and those inside $C$. For the vertices of $Q\setminus z_i$, reversing $C$ makes the outgoing edge of color 0 end either at $x_c$ or at a vertex $u$ strictly inside $C$. However the path of color 0 starting from any vertex inside $C$ has to pass by $x_c$; indeed the local Schnyder rule implies that $x_c$ is the only vertex on $C$ that can be incident to incoming edges of color 0 inside $C$. Overall the path of color 0 starting from any vertex of $Q\setminus z_i$ or any vertex inside $C$ has to pass by $x_c$, so that the path exits $R_b$ below. This ensures that $(F_0)$ still holds after reversing $C$. Hence, in the toroidal Schnyder wood, every cycle $\gamma_0$ of color 0 has to cross the top-river $R_t$. By the 2nd item of Lemma 7 it has to pass by vertex $u_0$ for $R_t$, which ensures that color 0 crosses color 2 (indeed $u_0$ belongs to $\gamma_2$), and that there is a unique cycle (and thus a unique connected component) in color 0.

We now consider the properties in color 1. Reversing $C$ makes $\gamma_1 := \partial R_b^e$ a cycle in color 1, which clearly crosses the cycle $\gamma_2$, hence color 1 crosses color 2; and by (3) in Lemma 3 we conclude that the toroidal Schnyder wood is crossing. It remains to check that the mono-chromatic component of color 1 is connected, i.e., to prove that $\gamma_1$ is the unique cycle in color 1. To establish this, it is clearly enough to prove the fact $(F_1)$ that, for every vertex $v$ of the cylindric triangulation $G$, the path of color 1 starting from $v$ either ends at $C_{in}$ or reaches $\gamma_1$. Clearly $(F_1)$ holds before reversing $C$ (for each vertex the outgoing path in color 1 ends at $C_{in}$), and we want to check that $(F_1)$ still holds after reversing $C$. It is enough to do the verification only for those vertices having changed their outgoing edge of color 1. These are the vertices of $Q\setminus u_{t-1}$ and the vertices inside $C$. For vertices of $Q\setminus u_{t-1}$ their outgoing edge of color 1 now ends on $Q \subset \gamma_1$ (see Figure 10) so that $(F_1)$ holds. For vertices inside $C$, due to the local Schnyder rule, their outgoing path of color 1 has to reach $C$ at $u_{t-1}$, because $u_{t-1}$ is the only vertex on $C$ that is incident to incoming edges of color 1 inside $C$. Since $u_{t-1} \in \gamma_1$ we conclude that $(F_1)$ still holds for these vertices as well. $\square$

The case where $(R_t, P_t)$ and $(R_b, P_b)$ are both of type C1 can be handled very similarly, by performing the rightmost $P_t$-constrained traversal of $R_t$, the leftmost $P_b$-constrained traversal of $R_b$, and reversing the specific directed cycle in $R_b$ that is guaranteed by the mirror-statement of the 3rd item in Lemma 3.

This concludes the proof of our main result, as stated in Theorem 1.

**Remark 12.** An alternative to our algorithm is given by Theorem 13 in [22], which allows to obtain a crossing Schnyder wood from a half-crossing one (such as computed by Proposition 9), however without guarantee of connectedness for the mono-chromatic components. It relies on the repeated reversal of carefully chosen directed cycles. As a comparison, our algorithm needs to reverse at most one directed cycle, and it is easy to implement in linear time (even though the overall proof of correctness is a bit involved).
<figure><img src="image_13.png" /><figcaption>Figure 11: (Left) runtime performances of Algorithm 1: average timings (computed over several runs) are expressed in seconds as a function of the size (millions of vertices). (Right) examples of genus 1 triangle meshes endowed with a toroidal Schnyder wood.</figcaption></figure>

# 7 Experimental results

## 7.1 Implementation and experiments

We have written Java implementations $^6$ of our algorithms and performed tests on genus 1 triangle meshes of various sizes (mostly taken from *Thingi10K* repository). Our algorithms for computing toroidal Schnyder woods are significantly simpler to analyze (in particular regarding the linear time complexity) and implement than previous solutions [17]. As confirmed by the runtime plots of Fig. 11, the approach based on vertex shelling leads to a very fast implementation: we can process more than $1M$ vertices per second (our experiments are run on a single core of a core i7-9700 cpu, allocating 8GB memory for the JVM, running Java 1.8 under Ubuntu Linux).

## 7.2 Conjectures on higher genus Schnyder woods: empirical results

We have conducted experiments providing an empirical confirmation of three conjectures involving Schnyder woods for triangulations in genus 1 and genus 2. We wrote a Java program that exhaustively generates all possible 3-orientations (see definition below in genus more than 1) and Schnyder woods for triangulations of genus $g \le 2$. Our generator is fast enough to process all tiny triangulations (generated using `surftri` [29], see Table 1) in a reasonable amount of time, allowing us to compute some statistics and test some conjectures.

<footnote>$^6$Datasets, runnable programs and source code (pure Java) are made available at: www.lix.polytechnique.fr/~amturing/software.html.</footnote>
<table><thead><tr><th>g=1</th><th>irreducible triang.</th><th>all triang.</th></tr></thead><tbody><tr><td>n=7</td><td>1</td><td>1</td></tr><tr><td>n=8</td><td>4</td><td>7</td></tr><tr><td>n=9</td><td>15</td><td>112</td></tr><tr><td>n=10</td><td>1</td><td>2109</td></tr><tr><td>n=11</td><td>-</td><td>37867</td></tr></tbody></table>

<table><caption>Table 1: Counting of simple triangulations of genus 1 and 2 (enumerated using *surftri* [29]). Center columns report the number of irreducible triangulations. Right columns report the number of all triangulations of a given size.</caption><thead><tr><th>g=2</th><th>irreducible triang.</th><th>all triang.</th></tr></thead><tbody><tr><td>n=7</td><td>-</td><td>-</td></tr><tr><td>n=8</td><td>-</td><td>-</td></tr><tr><td>n=9</td><td>-</td><td>-</td></tr><tr><td>n=10</td><td>865</td><td>865</td></tr><tr><td>n=11</td><td>26276</td><td>113506</td></tr></tbody></table>

## Connectedness of the three mono-chromatic graphs in genus 1

We have checked that all toroidal simple triangulations of size at most 11 admit a Schnyder wood for which the edges of the same color define a connected graph (having thus 3 mono-chromatic cycles, one for each color), providing an empirical answer to an open question stated in [17] (our algorithm of Section 6 guarantees a positive answer in two of the three colors). We also consider a second open question asked in [17] concerning the existence of crossing Schnyder woods satisfying a stronger requirement (referred to as *connected 3-cycles property*): the Schnyder wood is crossing, the three mono-chromatic components consist of a single connected component and the intersection of the three non trivial cycles is a single vertex <fnref n="7" />. Our experiments provide an empirical positive answer to this question (for $n \le 11$): we report in Figure 12 some statistics and the list of irreducible <fnref n="8" /> triangulations of genus 1, each endowed with a crossing Schnyder wood satisfying this stronger condition.

## Existence of Schnyder woods in genus 2

For a simple triangulation of genus $g \ge 1$, a *3-orientation* is an orientation such that for every vertex $v$ the out-degree is divisible by 3 and at least 3 (no sinks). In genus $g \ge 2$ some vertices must have degree more than 3, since $\sum_v (\deg(v) - 3) = 6g - 6$ according to the Euler relation. It is shown in [1] that any simple triangulation of genus $g \ge 2$ admits a 3-orientation. The following natural open question (asked in [22]) then arises: for every simple triangulation of genus $g \ge 2$, is it always possible to find a 3-orientation for which the edges can be colored so as to satisfy a *multiple* local Schnyder condition at every vertex (as depicted in Fig. 13)? In his PhD dissertation J. Suagee [28] shows that the answer is positive for every simple triangulation of genus $g \ge 2$ having edge-width at least $40(2^g - 1)$. We have checked that the answer is actually positive for every simple triangulations of genus 2 and $n \le 11$, suggesting that

<footnote n="7">⁷Observe that Thm. 9 in [17] guarantees the existence of three edge-disjoint mono-chromatic cycles crossing at a single vertex, but each mono-chromatic graph may consist of several disjoint components.</footnote>

<footnote n="8">⁸A triangulation is irreducible if no edge can be contracted without producing multiple edges.</footnote>
<figure><img src="image_14.png" /><figcaption>Figure 12: List of genus 1 irreducible triangulations (the embeddings are pro- vided in [23]). Each triangulation is endowed with a Schnyder wood satisfying the connected 3-cycles property computed by our generator. The bottom plots report some statistics computed by our generator.</figcaption></figure>
<figure><img src="image_15.png" /><figcaption>Figure 13: Planar layout of a genus 2 triangulation: it is endowed with two Schnyder woods satisfying the multiple Schnyder condition computed by our generator. In the left case vertex *a* has outgoing degree 9, while in the right one vertices *j* and *k* have outgoing degree 6. This triangulation admits 16.421.904 3-orientations and 509844 valid Schnyder woods.</figcaption></figure>

the assumption on the large edge-width is maybe unnecessary.

# 8 Concluding remarks

We expect that the construction of Section 3 can be extended to 3-connected toroidal maps using the notion of cylindric toroidal canonical ordering defined for the 3-connected case in [9], leading to a fast linear-time algorithm. As in the triangulated case, the obtained Schnyder woods should have the property of being balanced, which is instrumental in the bijective encoding of 3-connected toroidal maps [3] (indeed it relies on the computation of the *minimal* balanced Schnyder wood of the map, which can easily be obtained in linear time starting from an arbitrary balanced Schnyder wood).

# References

[1] Boris Albar, Daniel Gonçalves, and Kolja Knauer. Orienting triangulations. *J. Graph Theory*, 83(4):392–405, 2016. URL: https://doi.org/10.1002/jgt.22005.

[2] Olivier Bernardi and Nicolas Bonichon. Catalan's intervals and realizers of triangulations. *Journal of Combinatorial Theory, Series A*, 116(1):55–75, 2009. 22 pages. URL: https://hal.archives-ouvertes.fr/hal-00143870.

[3] Nicolas Bonichon, Éric Fusy, and Benjamin Lévêque. A bijection for essentially 3-connected toroidal maps. *Eur. J. Comb.*, 95:103290, 2021. URL: https://doi.org/10.1016/j.ejc.2020.103290, doi:10.1016/J.EJC.2020.103290.
[4] Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perkovic. Plane spanners of maximum degree six. In *Automata, Languages and Programming, 37th International Colloquium, ICALP 2010*, pages 19–30, 2010. URL: https://doi.org/10.1007/978-3-642-14165-2_3.

[5] Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Edge partition of toroidal graphs into forests in linear time. In *ICGT*, volume 22, pages 421–425, 2005.

[6] Nicolas Bonichon and Benjamin Lévêque. A bijection for essentially 4-connected toroidal triangulations. *Electron. J. Comb.*, 26(1):1, 2019. doi: 10.37236/7897.

[7] U. Brandes and D. Wagner. A linear time algorithm for the arc disjoint menger problem in planar directed graphs. *Algorithmica*, 28(1):16–36, 2000. URL: https://doi.org/10.1007/s004530010029.

[8] Enno Brehm. 3-orientations and Schnyder 3-tree-decompositions. *Master's Thesis, FB Mathematik und Informatik, Freie Universität Berlin*, 2000.

[9] Luca Castelli Aleardi, Olivier Devillers, and Éric Fusy. Canonical ordering for graphs on the cylinder, with applications to periodic straight-line drawings on the flat cyclinder and torus. *J. Comput. Geom.*, 9(1):391–429, 2018. URL: https://doi.org/10.20382/jocg.v9i1a14.

[10] Luca Castelli Aleardi, Éric Fusy, and Thomas Lewiner. Schnyder woods for higher genus triangulated surfaces, with applications to encoding. *Discrete & Computational Geometry*, 42(3):489–516, 2009. URL: https://hal.inria.fr/hal-00712046v1.

[11] Vincent Despré, Daniel Gonçalves, and Benjamin Lévêque. Encoding toroidal triangulations. *Discrete & Computational Geometry*, 57(3):507–544, 2017. URL: https://doi.org/10.1007/s00454-016-9832-0.

[12] Raghavan Dhandapani. Greedy drawings of triangulations. *Discrete & Computational Geometry*, 43(2):375–392, 2010. URL: https://doi.org/10.1007/s00454-009-9235-6.

[13] Stefan Felsner. Convex drawings of planar graphs and the order dimension of 3-polytopes. *Order*, 18(1):19–37, 2001.

[14] Stefan Felsner. Geodesic embeddings and planar graphs. *Order*, 20(2):135–150, 2003. URL: https://doi.org/10.1023/B:ORDE.0000009251.68514.8b.

[15] Stefan Felsner and Florian Zickfeld. On the number of planar orientations with prescribed degrees. *Electr. J. Comb.*, 15(1), 2008.
[16] Éric Fusy and Benjamin Lévêque. Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth. *J. Comb. Theory A*, 175:105270, 2020. URL: https://doi.org/10.1016/j.jcta.2020.105270, doi:10.1016/J.JCTA.2020.105270.

[17] Daniel Gonçalves and Benjamin Lévêque. Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations. *Discrete & Computational Geometry*, 51(1):67–131, 2014. URL: http://dx.doi.org/10.1007/s00454-013-9552-7.

[18] Goos Kant. Drawing planar graphs using the canonical ordering. *Algorithmica*, 16(1):4–32, 1996. URL: https://doi.org/10.1007/BF02086606.

[19] Samir Khuller, Joseph Naor, and Philip N. Klein. The lattice structure of flow in planar graphs. *SIAM J. Discret. Math.*, 6(3):477–490, 1993. doi:10.1137/0406038.

[20] Kolja Knauer, Daniel Gonçalves, and Benjamin Lévêque. On the structure of Schnyder woods on orientable surfaces. *J. Comput. Geom.*, 10(1):127–163, 2019. URL: https://doi.org/10.20382/jocg.v10i1a5.

[21] Stephen G. Kobourov. Canonical orders and schnyder realizers. In *Encyclopedia of Algorithms*, pages 277–283. Springer, 2016. URL: http://dblp.uni-trier.de/rec/bib/reference/algo/Kobourov16.

[22] Benjamin Lévêque. *Generalization of Schnyder woods to orientable surfaces and applications*. Hdr thesis, Université Grenoble Alpes, 2016. URL: https://tel.archives-ouvertes.fr/tel-01488943.

[23] Bojan Mohar and Carsten Thomassen. *Graphs on Surfaces*. Johns Hopkins, 2001.

[24] Dominique Poulalhon and Gilles Schaeffer. Optimal coding and sampling of triangulations. *Algorithmica*, 46(3-4):505–527, 2006. doi:10.1007/s00453-006-0114-8.

[25] Neil Robertson and Paul D. Seymour. Graph minors. VI. disjoint paths across a disc. *J. Comb. Theory, Ser. B*, 41(1):115–138, 1986. URL: https://doi.org/10.1016/0095-8956(86)90031-6.

[26] Walter Schnyder. Planar graphs and poset dimension. *Order*, pages 323–343, 1989.

[27] Walter Schnyder. Embedding planar graphs on the grid. In *Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms*, volume 90, pages 138–148, 1990. URL: http://departamento.us.es/dma1euita/PAIX/Referencias/schnyder.pdf.

[28] Jason Suagee. *Existence and Construction of Schnyder Orientations over a Large Class of Higher Genus Surface Triangulations*. PhD thesis, George Washington University, 2021.
[29] Thom Sulanke. Generating maps on surfaces. *Discret. Com-put. Geom.*, 57(2):335–356, 2017. URL: https://doi.org/10.1007/s00454-016-9853-8.