Computation of Toroidal Schnyder Woods Made Simple and Fast: From Theory to Practice

Addressing two questions left open in [22, 27], 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 ³³3In the planar case there exists a linear time algorithm for computing Schnyder woods via canonical orderings [8, 26] performing vertex shellings: the fact that such an algorithm also exists in the toroidal case has been left as an open question in [27]. 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:

As far as we know, our approach leads to the first implementation for computing toroidal Schnyder woods: previous solutions [22, 27] 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 [1, 22] regarding the existence of Schnyder woods for higher genus surfaces.

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,\mathrm{\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$.

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 $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 (see [13] for the proof of the Lemma below).

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,\mathrm{\dots },x_{r-1}\}$ and ${\partial }^{e}R=\{z_0,z_1,z_2,\mathrm{\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,\overline{x})$, where $\overline{x}\in {\partial }^{i}R$, and every vertex $x\in {\partial }^{i}R$ has an incident edge $(x,\overline{z})$, where $\overline{z}\in {\partial }^{e}R$ (such edges are called non-trivial chords of $R$).

Let us assume that $R$ is provided with a chordless path $P=\{u_0,\mathrm{\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):

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 (see [13] for the proof).

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.

Let $𝒯$ be a simple toroidal triangulation. We now describe the algorithm computing a half-crossing Schnyder woods of $𝒯$; the complete pseudo-code is provided in Algorithm 3, see also Figure 8 for an illustration on an example. After cutting $𝒯$ along a non-contractible and chordless cycle $\mathrm{\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 $𝒯$. 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 $\mathrm{\Gamma }$ (it may share edges with $\mathrm{\Gamma }$ but reaches it only once from the left). If $C$ crosses any cycle of color $2$, then we output $S(𝒯)$. Otherwise we need a second pass. Let ${\gamma }_2$ be an arbitrary 2-cycle. Note that ${\gamma }_2$ winds once around $\mathrm{\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 $\mathrm{\Gamma }$). Hence, if we cut ${\gamma }_2$ along $\mathrm{\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(𝒯)$ 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$ (as expressed by Proposition 9).

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.

Given a toroidal simple triangulation $𝒯$, as before the first step consists in cutting $𝒯$ along a chordless non-contractible cycle $\mathrm{\Gamma }$, yielding a cylindric triangulation $G$. Since $\mathrm{\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 $\mathrm{\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 $𝒯$. 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 $\mathrm{\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^{\prime },P^{\prime })$, not to be of type C2, and the other one, denote it by $(R^{\prime \prime },P^{\prime \prime })$, not to be of type C1. Then we perform a right-most traversal for $(R^{\prime },P^{\prime })$, and a left-most traversal for $(R^{\prime \prime },P^{\prime \prime })$. After these updates on the Schnyder woods for the two rivers, and by the arguments of Section 5, the toroidal Schnyder wood of $𝒯$ now has the property that cycles of color $1$ (resp. $0$) cross cycles of color $2$ thanks to $R^{\prime }$ (resp. $R^{\prime \prime }$), 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 $\mathrm{\Gamma }$.

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.

We have written Java implementations ⁵⁵5 Datasets, runnable programs and source code (pure Java) are made available at:
www.lix.polytechnique.fr/$\sim$amturing/software.html. 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 [22]. As confirmed by the runtime plots of Fig. 10, 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).

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 [34], see Table 1) in a reasonable amount of time, allowing us to compute some statistics and test some conjectures.