<figure><img src="image_79.png" /><figcaption>Figure 5.6: Complete execution of the algorithm computing an x-periodic drawing of a cylindrical simple triangulation with no chordal edge at $B_{\text{inn}}$. The vertices are processed in increasing label (the canonical ordering is the one computed in Fig. 3.13).</figcaption></figure>

$P_\ell \cap P_r$ is increased by 2). After these stretching operations <fnref n="3" />, whose effect is to make the slopes of $e_\ell$ and $e_r$ strictly smaller than 1 in absolute value, we insert, as in Case (1), the vertex $v_k$ at the intersection of the ray of slope 1 starting from $a_k$ and the ray of slope $-1$ starting from $b_k$, and we connect $v_k$ to all vertices of $\gamma$ by segments.

Note that in the two cases (1) and (2), the two rays from $a_k$ and $b_k$ actually intersect at a grid point since the Manhattan distance between any two vertices on $B_{k-1}$ is even. A complete execution of this algorithm is illustrated in Fig. 5.6.

One can easily check that the drawing remains crossing-free: this relies on the fact that all edges of the upper boundary have slope at most 1 in absolute value, and on the following inductive property (similar to the one used in [FPP90]), which is maintained at each step k from 1 to n:

**PI:** for each edge e on $B_k$ (the upper boundary of $G_k$), let $P_e$ be the root-path of e* in $F^*$, let $E_e$ be the set of edges dual to edges in $P_e$, and let $\delta_e$ be any nonnegative integer. Then the drawing remains crossing-free after successively increasing by $\delta_e$ the x-span of all edges of $E_e$, for all $e \in B_k$.

**BOUNDS ON THE GRID-SIZE.** Let us denote by w the width and by h the height of the cylinder on which G is drawn. If $|\Gamma_{\text{inn}}| = t$ then the initial cylinder is $2t \times 0$; and at each vertex insertion, the grid-width grows by 0 or 2. Hence $w \le 2n$. In addition, due to the slope conditions (slopes of boundary-edges are at most 1 in absolute value), the vertical span of every edge e is not larger than the current width at the time when e is inserted in the drawing. Hence, if we denote by v the vertex of $\Gamma_{\text{ext}}$ that is closest (at distance d) from $\Gamma_{\text{inn}}$, then the ordinate of v is at most $d \cdot (2n)$. And due

<footnote n="3">³ In the FPP algorithm for planar triangulations, the step to make the (absolute value of) slopes of $e_\ell$ and $e_r$ smaller than 1 is formulated as a shift of certain subgraphs described in terms of the underlying forest F. The extension of this formulation to the cylinder would be quite cumbersome. We find the alternative formulation with strip insertions more convenient for the cylinder. In addition it also gives rise to a very easy linear-time algorithm, whose practical performances are extremely good, as confirmed by the running times reported in Fig. 5.1. Another linear-time version of the FPP algorithm is given in [CP95].</footnote>
to the slope conditions, the vertical span of $\Gamma_{\text{ext}}$ in the drawing is at most $w/2 \le n$. Hence the grid-height is at most $n(2d+1)$.

**LINEAR-TIME COMPLEXITY.** An important remark is that, instead of computing the x-coordinates and y-coordinates of vertices in the drawing, one can compute the y-coordinates of vertices and the x-span of edges (as well as the knowledge of which extremity of the edge is the left-end vertex and which extremity is the right-end vertex). In a first pass, for $k$ from 1 to $n$, one computes the y-coordinates of vertices and the x-span $r_e$ of each edge $e \in G$ at the time $t = k$ when it appears on $G_k$ (as well one gets to know which extremity of $e$ is the left-end vertex). Afterwards if $e \notin F$, the x-span of $e$ might further increase due to insertion of new vertices; let $s_e$ be the total further increase undergone by $e$. Note that for each edge $e$ not in $F$, if $e \notin \Gamma_{\text{ext}}$ there is a certain step $k$ such that $e \in B_{k-1}$ and $e \notin B_k$. Let $w_e \in \{0,1,2\}$ be defined as the stretch (increase of x-span) that $e$ undergoes just before adding $v_k$ to the drawing; in case $e \in \Gamma_{\text{ext}}$ no such step $k$ exists and we assign $w_e = 0$. We call $w_e$ the weight of $e$ (the quantities $w_e$ can be computed in a first pass, together with the quantities $r_e$). Let $P$ be the root-path of $e^*$. When stretching $e$ just before adding $v_k$, all edges dual to edges of $P$ undergo the same stretch, by $w_e$. In other words, if we denote by $T_e^*$ the subtree of $F^*$ hanging from $e^*$ (including $e^*$), and denote by $W_e$ the total weight of the dual of the edges in $T_e^*$, then $s_e = W_e$. Hence the total x-span of each edge $e \in G$ is given by $r_e + s_e$, where $s_e = 0$ if $e \in F$ or $e \in \Gamma_{\text{ext}}$, and $s_e = W_e$ if $e \notin F$ and $e \notin \Gamma_{\text{ext}}$. Since all quantities $s_e$ can easily be computed in linear time from the quantities $w_e$, starting from the leaves and going up to the roots of $F^*$, this gives a linear-time algorithm.

To sum up, for the case of simple cylindrical triangulations with no chord at $\Gamma_{\text{inn}}$ (and with no loops and no multiple edges) we can state the following:

**Proposition 5.1 ([CDF18b])** Given a simple cylindrical triangulation $G$ with no chordal edge at $\Gamma_{\text{inn}}$, one can compute in linear time a crossing-free straight-line drawing of $G$ on an $x$-periodic regular grid $Z/w\mathbb{Z} \times [0..h]$ where —with $n$ the number of vertices of $G$ and $d$ the edge-distance between the two boundaries— $w \le 2n$ and $h \le n(2d+1)$, such that the upper boundary is a broken line monotone in $x$ formed by segments of slope in $\{+1,-1,0\}$ and the lower boundary is an horizontal line.

**Remark 1** Note that our algorithm can be seen as an extension of the FPP algorithm, which works for simple planar quasi-triangulations, i.e., simple graphs embedded in the plane with triangular inner faces and a polygonal outer face (see Fig. 5.7).

**Remark 2** For each edge $e$ of $\Gamma_{\text{inn}}$, let $r_e$ be the initial horizontal stretch of $e$ in the drawing procedure (an even number, classically $r_e = 2$ to have a compact drawing). And let $t_e$ be the final horizontal stretch in the drawing procedure. The vectors $R = (r_e)_{e \in \Gamma_{\text{inn}}}$ and $T = (t_e)_{e \in \Gamma_{\text{inn}}}$ are called initial-stretch and final-stretch vectors relative to the drawing of $G$ (endowed with a given canonical ordering). Then the vector $S := T - R$ is an invariant, it does not depend on $R$ since $s_e = t_e - r_e$ just depends on the underlying forest and dual forest given by the canonical ordering. Hence, if with $R$ as initial stretch-vector we obtain a drawing with final-stretch vector $T$, then for any vector $T'$ of the form $T + 2V$ —with $V$ a vector of non-negative integers— we can obtain a drawing with final-stretch vector $T'$, by taking $R' = R + 2V$ as initial-stretch vector instead of $R$.

<figure><img src="image_80.png" /><figcaption>Figure 5.7: The FPP algorithm for simple planar quasi-triangulations can be recovered from our algorithm. Given a simple planar quasi-triangulation $Q$, we can turn it into a cylindrical simple triangulation $G$ by adding a vertex of degree 2 connected to the two ends of the root-edge. Then the FPP drawing of $Q$ is recovered from the periodic drawing of $Q$ upon deleting the added vertex.</figcaption></figure>
<figure><img src="image_81.png" /><figcaption>Figure 5.9: Left-side: the shelling procedure for an essentially simple loopless cylindrical triangulation $G$ with no chord at $\Gamma_{\text{inn}}$; the last drawing shows the underlying forest and dual forest. Right-side: the incremental drawing algorithm.</figcaption></figure>

<figure><img src="image_82.png" /><figcaption>Figure 5.8: When 2-cycles are allowed, the additional case shown here can occur for the transition from $G_{k-1}$ to $G_k$.</figcaption></figure>

**ALLOWING FOR NON-CONTRACTIBLE 2-CYCLES.** Our method based on a canonical ordering and incremental drawing algorithm can be easily extended to deal with an essentially simple cylindrical triangulation $G$, having no loops but possibly with non-contractible 2-cycles. The definition of canonical ordering for $G$ is exactly the same as for simple cylindrical triangulations, adding the possibility that $G_k$ is obtained from $G_{k-1}$ as shown in Fig. 5.8. Such a canonical ordering can be computed by a shelling procedure that extends the one of Section 3.3. A 2-cycle is called *internal* if its two incident vertices are not both on the outer boundary. This time, a vertex on the outer boundary and not on the inner boundary is called *free* if it is not incident to a chord nor incident to an internal 2-cycle.

The shelling procedure consists in choosing a free vertex at each step, and deleting it together with its incident edges, until there just remains the inner boundary and the cylindrical map is reduced to a cycle. (the argument that shows the existence of free vertices is omitted here, and a detailed presentation is given in [CDF18b]).

A linear time algorithm is also readily obtained by maintaining, for each outer vertex, how many neighbours on $\Gamma_{\text{ext}}$ it has and how many internal 2-chords it is incident to. Note that such a canonical ordering also induces an underlying forest $F$ and the dual forest $F^*$. These can be computed on the fly during the shelling procedure, in the same way as for simple cylindrical triangulations. Finally, the incremental drawing algorithm (and linear complexity using the dual forest) works exactly in the same way as for cylindrical simple triangulations. An example is shown in Fig. 5.9. The grid bounds are also the same as for simple triangulations (the arguments to obtain the bounds in the simple case did not use the fact that there are no 2-cycles). So this gives Proposition 5.1 for essentially simple triangulations with no loops. Finally, note that Remark 2 still holds here (the arguments are the same).

**ALLOWING FOR NON-CONTRACTIBLE LOOPS.** We finally explain how to deal with non-contractible loops. Our strategy is not to extend the notion of canonical ordering but simply to decompose (at the loops, which are nested) such a cylindrical map into a "tower" of components, where the only loops in each component are at the boundary-faces. Let $G$ be an essentially simple
cylindrical triangulation with $n$ vertices and at least one loop. There are a few cases to consider:

(a) $\Gamma_{\text{inn}}$ is the unique loop of G. In that case, the algorithm of Section 3.3 (canonical ordering, shelling procedure, and incremental drawing procedure) works in the same way, see Fig. 5.10 for an example. Let $2m$ be the width of the drawing. By the arguments of Remark 2, for any $m' \ge m$, G has a periodic drawing of width $2m'$ and height at most $m'(2d+1)$, with $d$ the edge-distance between the two boundaries.

(b) $\Gamma_{\text{ext}}$ is a loop, $\Gamma_{\text{inn}}$ is possibly a loop, and there are no other loops. Assume $\Gamma_{\text{ext}}$ is a loop and G is not reduced to that loop (i.e., $\Gamma_{\text{ext}} \ne \Gamma_{\text{inn}}$). Let $u$ be the vertex incident to the loop (note that $u$ is not on $\Gamma_{\text{inn}}$ since there is no chord at $\Gamma_{\text{inn}}$), and let $c$ be the innermost 2-cycle incident to $u$. Cutting along $c$ (see Fig. 5.11), we obtain two components: a planar triangulation $T$ and a cylindrical essentially simple triangulation $G'$ such that: $G'$ has no loop except possibly at $\Gamma_{\text{inn}}$, $G'$ has outer degree 2 and $u$ is a free vertex for $G'$. Hence there is a canonical ordering for $G'$ such that $u$ is the first shelled vertex. Take a periodic drawing of $G'$ for this canonical ordering and take an FPP drawing of $T$. The widths of the respective drawings are even numbers, denoted $2n_1$ and $2n_2$. Let $m = \max(n_1, n_2)$. By the arguments of Remark 2 it is possible to redraw the graph that has the smaller grid-width so that it gets width $2m$, after which both drawings are of width $2m$. Then the drawing of $T$ (taken upside down) fits into the upper boundary of $G'$ yielding a periodic drawing of $G$ of width $2m$, see Fig. 5.11. The height of the drawing is at most $2dm \le 2dn$, where $d$ is the edge-distance between the two boundaries (indeed, in the usual bound $h \le (2d+1)m$, the +1 in the parenthesis is due to the vertical extension of the upper boundary, which is 0 here).

(c) General case. Here we assume there is at least one loop. Let $\ell_1, \dots, \ell_r$ be the sequence of nested loops of $G$, with $\ell_1$ the innermost loop and $\ell_r$ the outermost loop; and let $G^{(0)}, \dots, G^{(r)}$ be the $r+1$ components that result from cutting successively along all these loops. For $i \in [0..r]$ let $d_i$ be the edge-distance between the two boundaries in $G^{(i)}$; and let $d$ be the edge-distance between the two boundaries of $G$. Note that $d = \sum_i d_i$. Each component $G_i$ has loops only at the boundary-face contours, hence has a periodic drawing (according to cases (a) and (b)) such that boundaries that are loops are drawn as horizontal lines. Let $2n_1, \dots, 2n_r$ be the widths of the drawings of $G^{(1)}, \dots, G^{(r)}$ thus obtained. Let $m = \max(n_1, \dots, n_r)$. By the arguments of Remark 2, each of the graphs $G^{(i)}$ can be redrawn so as to have width $2m$. Stacking up all these drawings we obtain a periodic drawing of $G$ of width $2m$, see Fig. 5.12. Regarding the grid size, the width is $2m$, with clearly $m \le n$, and the height of the drawing of $G_i$ is at most $2md_i$ for $i \in [0..r-1]$ and at most $m(2d_r+1)$ for $i=r$. Hence the total height is at most $m(2d+1) \le n(2d+1)$. This establishes Proposition 5.1.

### 5.3.2 Drawing cylindrical triangulations having chords at $\Gamma_{\text{inn}}$.

We finally explain how to draw a cylindrical essentially simple triangulation when allowing for chords incident to $\Gamma_{\text{inn}}$. It is good to view $B_{\text{ext}}$ as the top boundary-face and $B_{\text{inn}}$ as the bottom boundary face, and imagine a standing cylinder. For each chord $e$ at the cycle $\Gamma_{\text{inn}}$, the component under $e$, denoted $Q_e$, is the face-connected part of $G$ that lies below $e$; such a component is a quasi-triangulation (polygonal outer face, triangular inner faces)

<figure><img src="image_83.png" /><figcaption>Figure 5.10: Drawing algorithm when the inner boundary is the unique loop.</figcaption></figure>
<figure><img src="image_84.png" /><figcaption>Figure 5.11: Drawing algorithm when the outer face contour is a loop (and there is no other loop except possibly at $\Gamma_{\text{inn}}$): the map is split along the innermost 2-cycle (the initial x-span of T is taken to be 4 instead of 2 so that the drawings of Q and $G'$ fit together).</figcaption></figure>

<figure><img src="image_85.png" /><figcaption>Figure 5.12: Drawing an essentially simple triangulation $G$ (no chord at $\Gamma_{\text{inn}}$); $G$ is first decomposed at its loops; each component is drawn so that the component-drawings have the same width, and can be stacked up to obtain a periodic drawing of $G$.</figcaption></figure>
<figure><img src="image_86.png" /><figcaption>FPP layout of $Q_e$</figcaption></figure>

<caption>Figure 5.13: Drawing a cylindrical triangulation with chords at $\Gamma_{\text{inn}}$ (essentially simple with loops and 2-cycles in the annular representation). To make enough space to place the component under $e$, one takes 4 (instead of 2) as the initial x-span of $e$.</caption>

rooted at the edge $e$. A chordal edge $e$ of $\Gamma_{\text{inn}}$ is *maximal* if the component $Q_e$ under $e$ is not strictly included in the component under another chord at $\Gamma_{\text{inn}}$. The *FPP-size* $|e|$ of such an edge $e$ is defined as the width of the FPP drawing of $Q_e$. If we delete the component under each maximal chordal edge (i.e., delete everything from the component except for the chordal edge itself) we get a new bottom cycle $C'_0$ that is chordless, so we can draw the reduced cylindrical triangulation $G'$ as explained in the previous section. Let $w_e$ be the width of each edge $e$ of $C'_0$ in this drawing. According to Remark 2, we can redraw $G'$ such that each edge $e \in C'_0$ that is chordal in $G$ has width $\ell(e)$, with $\ell(e)$ defined as the smallest integer that is at least $\max(w_e, |e|)$ and such that $\ell(e) - w_e$ is even (note that $\ell(e) \le \max(w_e, |e|+1)$).

Then for each maximal chord $e$ of $C_0$, we draw the component $Q_e$ under $e$ using the FPP algorithm. This drawing has width $|e|$, with $e$ as horizontal bottom edge of length $|e|$ and with the other outer edges of slopes in $\pm 1$. We shift the left-extremity of $e$ to the left so that the drawing of $Q_e$ gets width $\ell(e)$, then we rotate the drawing of $Q_e$ by 180 degrees and plug it into the drawing of $G'$, see Fig. 5.13. The overall drawing of $G$ is clearly planar and achieves good vertex resolution, as expressed by the result below, which generalizes Proposition 5.1 (the analysis of the grid-size is omitted here; more details can be found in [CDF18b]).

**Theorem 5.2 ([CDF18b])** For each essentially simple cylindrical triangulation $G$, one can compute in linear time a crossing-free straight-line drawing of $G$ on an $x$-periodic regular grid $\mathbb{Z}/w\mathbb{Z} \times [0..h]$ where —with $n$ the number of vertices of $G$ and $d$ the edge-distance between the two boundaries— $w \le 2n$ and $h \le n(2d+1)$, such that the upper boundary is a broken line monotone in $x$ formed by segments of slope in $\{+1,-1,0\}$ and the lower boundary is an horizontal line.

### 5.3.3 Periodic drawings on the torus

Combining the results described in previous section with the computation of a tambourine, we can obtain a linear-time algorithm for computing periodic straight-line drawings of toroidal graphs. Our main result, stated in the triangulated case, is the following:

**Theorem 5.3** For each essentially simple toroidal triangulation $\mathcal{T}$, one can compute in linear time a crossing-free straight-line drawing of $\mathcal{T}$ on a periodic regular grid $\mathbb{Z}/w\mathbb{Z} \times \mathbb{Z}/h\mathbb{Z}$, where —with $n$ the number of vertices and $e_w$ the edge-width— $w \le 2n$ and $h \le 1+2n(e_w+1) = O(n^{3/2})$.
<figure><img src="image_87.png" /><figcaption>Figure 5.14: The main steps for drawing of a toroidal triangulation: first remove the edges inside a tambourine; then draw the obtained cylindrical triangulation, and insert the edges of the tambourine back into the drawing.</figcaption></figure>

The fact that the grid size is $w \times h = O(n^{5/2})$ relies on an upper bound on the edge-width proved in [AH78] (namely $e_w \le \sqrt{2n}$).

### DRAWING TOROIDAL TRIANGULATIONS: OVERVIEW OF THE PROOF.
Let $\mathcal{T}$ be an essentially simple toroidal triangulation with $n$ vertices, and let $\Gamma_1, \Gamma_2$ be a tambourine of $\mathcal{T}$ (as defined in Section 2.1.2). By deleting the edges that are strictly inside the tambourine, one obtains a cylindrical triangulation $G$ with $\Gamma_1$ the outer boundary and $\Gamma_2$ the inner boundary.

We can apply the drawing algorithm of Theorem 5.3 to obtain a periodic drawing of $G$ on an $x$-periodic grid $\mathbb{Z}/w\mathbb{Z} \times [0..h]$. If we augment the height $h$ of the drawing to $h' = h + w + 1$, and then wrap the $x$-periodic grid $\mathbb{Z}/w\mathbb{Z} \times [0..h]$ into a periodic grid $\mathbb{Z}/w\mathbb{Z} \times \mathbb{Z}/h'\mathbb{Z}$, and finally insert the edges inside the tambourine as segments (we insert the edges in the tambourine $T$ in the unique way such that, looking from bottom to top, at least one edge in $T$ goes strictly to the right, and all edges going strictly to the right have $x$-span at most $w$; in this way it is easy to check that the $x$-span of all edges in $T$ is at most $w$). Then the slope properties —edges on $\Gamma_1$ and $\Gamma_2$ have slope at most 1 in absolute value while edges inside the tambourine have slopes greater than 1 in absolute value— ensure that the resulting drawing is crossing-free. Note that it is actually enough to augment the height by the least value such that the edges of $T$ have slope greater than 1 in absolute value. See Fig. 5.14 for an example.

We now argue that we can find a tambourine $\Gamma_1, \Gamma_2$ so that the distance between the two boundaries $\Gamma_1$ and $\Gamma_2$ (in $G$) is smaller than the edge-width of $\mathcal{T}$; and we can find it *without having to compute* a curve $\Gamma_{\min}$ realizing the edge-width (this is crucial to obtain a linear-time complexity, since it is not known how to find such a curve $\Gamma_{\min}$ in linear time). Indeed, let $\{\Gamma_a, \Gamma_b\}$ be a basis of non-contractible cycles of $\mathcal{T}$ (computable in linear time, using for instance a cut-graph). Then at least one of $\Gamma_a$ or $\Gamma_b$ is not homotopic (parallel) to $\Gamma_{\min}$. Let $\Gamma$ be one among $\{\Gamma_a, \Gamma_b\}$ that is not homotopic to $\Gamma_{\min}$, and let $\Gamma_1, \Gamma_2$ be a (computable) tambourine parallel to $\Gamma$. Since we are on the torus, $\Gamma_{\min}$ has to cross the tambourine $\Gamma_1, \Gamma_2$. Hence, the distance between the boundary-cycles (after deleting edges in the tambourine $\Gamma_1, \Gamma_2$) is smaller than the edge-width. In other words, if we choose the one cycle among $\{\Gamma_a, \Gamma_b\}$ that yields the smaller distance between the two boundaries of $G$, then this distance $d$ is smaller than the edge-width $e_w$ of $\mathcal{T}$. The grid-size of the drawing of $G$ satisfies $w \le 2n$ and $h \le 2n(d+1)$, and the grid-size of the drawing of $\mathcal{T}$ is $w, h'$ where $h' \le h+w+1 \le 2n(d+1)+2n+1 =$
<figure><img src="image_88.png" /><figcaption>Figure 5.15: Drawing essentially 3-connected toroidal maps: first remove the edges inside a tambourine, and then draw the obtained (essentially) internally 3-connected cylindrical map; at the end insert the edges of the tambourine back into the drawing.</figcaption></figure>

1 + 2n(d + 2). Since d < e<sub>w</sub> we conclude that the grid-height of the drawing of T is bounded by 1 + 2n(e<sub>w</sub> + 1), as stated in Theorem 5.3.

**DRAWING ESSENTIALLY 3-CONNECTED GRAPHS** It turns out that these kind of technics described above for triangulations are also suitable to deal with the more general case of essentially 3-connected toroidal maps: the key idea is to make use of our generalization of the notion of canonical orderings for 3-connected planar graphs and the related grid drawing algorithm by [Kan96] (the proof is omitted here and a detailed discussion can be found in [CDF18b]).

The validity of our construction also relies on the fact that given an es-
sentially 3-connected toroidal map $\mathcal{M}$ and a non-contractible cycle $\Gamma$, it is
possible to compute in linear time a tambourine $\Gamma_1, \Gamma_2$ of $\mathcal{M}$ whose two cy-
cles are homotopic to $\Gamma$. The proof of this fact, that extends the result for
triangulations mentioned in Section 2.1.2, can be found in [CDF18b].

Our main result, illustrated by the pictures in Fig. 5.15, is stated below:

**Theorem 5.4 (Castelli Aleardi, Devillers, and Fusy [CDF18b])** For each essentially 3-connected toroidal map $\mathcal{M}$, one can compute in linear time a weakly convex crossing-free straight-line drawing of $\mathcal{M}$ on a periodic regular grid $\mathbb{Z}/w\mathbb{Z} \times \mathbb{Z}/h\mathbb{Z}$, where —with $n$ the number of vertices and $c$ the face-width— $w \le 2n$ and $h \le 1+2n(c+1)$. Since $c \le \sqrt{2n}$, the grid area is $O(n^{5/2})$.

The bound on the grid-size relies on the fact that we can triangulate an essentially simple toroidal graph $\mathcal{M}$, by adding edges but not adding vertices, so as to obtain an essentially simple toroidal triangulation $\tilde{\mathcal{M}}$. As already mentioned (and shown in [AH78]), $\tilde{\mathcal{M}}$ has a non-contractible cycle $\gamma$ of length at most $\sqrt{2n}$: observe that this cycle can be locally deformed into a proper non-contractible curve meeting $\mathcal{M}$ at the vertices on $\gamma$.

A periodic straight-line drawing on the flat torus is said to be weakly convex if all corners have angle at most $\pi$.
<figure><img src="image_89.png" /><figcaption>Figure 5.16: A 4-scheme triangulation G (corners are white) and a straight-frame drawing of G (bottom). G is not balanced, as $|S_1| \neq |S_3|$.</figcaption></figure>

## 5.4 OUR CONTRIBUTION: PERIODIC STRAIGHT-FRAME DRAWINGS

We now address the problem of computing toroidal drawings adding a further constraint: we aim at obtaining a planar straight-frame drawing of a toroidal triangulation, for which the edges are not allowed to cross the boundary of the flat torus<fnref n="4" />.

We follow the strategy adopted in [DGK11] for the toroidal case based on the following fact: any simple toroidal triangulation $\mathcal{T}$ can be cut along a subgraph (cut-graph) such that the resulting unfolded graph $G$ is naturally a quasi-triangulation (referred to as *4-scheme triangulation* and shortly denoted *4ST*) with 4 marked outer vertices, called *corners*, such that each path of the outer face contour between two consecutive corners is chordless. We will denote by $S_1, \dots, S_4$ these outer paths (in clockwise order around the outer face), and denote by $|S_i|$ the length of $S_i$. Observe that cutting a toroidal triangulation in this way yields a *balanced* 4-scheme triangulation, having the additional property that $|S_1| = |S_3|$ and $|S_2| = |S_4|$.

So, our initial problem (drawing a toroidal triangulation) translates into the problem of computing a *straight-frame periodic drawing* of a (balanced) 4-scheme triangulation $G$ (refer to Fig. 5.16 for an illustration): the abscissas of vertices of the same rank along $S_1$ and $S_3$ (ordered from left to right) should coincide, and the ordinates of vertices of the same rank along $S_2$ and $S_4$ (ordered from bottom to top) should also coincide. When $G$ arises from a toroidal triangulation $\mathcal{T}$, this is exactly the condition to satisfy so that the drawing lifts to a periodic representation of $\mathcal{T}$ on the flat torus.

In this section we provide a short overview of the steps leading to our main result stated below (its validity relies on several technical lemmas whose proofs are omitted here: more details can be found in [CFK14]):

**Theorem 5.5 (Castelli Aleardi, Fusy, and Kostrygin [CFK14])** Each balanced 4-scheme-triangulation admits a periodic straight-frame drawing on a regular grid of size $O(n^4 \times n^4)$. The drawing can be computed in linear time.

Our algorithm makes use of a new decomposition strategy for 4-scheme triangulations: we cut the triangulation into two components A, B along a certain path “close to” $S_3$, the “lower part” B is drawn using the algorithm of Duncan et al. [DGK11] specially adapted for our purpose (to make the ordinates of matching vertices in the lower parts of $S_2$ and $S_4$ coincide), and then we draw the “upper part” A with a suitably fixed outer frame (this is the most technical part, which requires a further decomposition of A into several pieces).

### 5.4.1 Related works: description of the algorithm of Duncan et al. [DGK11]

Define a *half-4-scheme triangulation*, shortly written $H_4\text{ST}$, as a graph $H$ embedded in the plane satisfying all conditions of a 4ST, except that the paths $S_2$ and $S_4$ are allowed to be empty, and the path $S_3$ is allowed to have chords and to meet $S_1$; $S_1$ is called the *bottom-path* of $H$. Given a 4ST $G$, an important ingredient in [DGK11] is the *river lemma*, which guarantees the existence of a so-called *river*, that is, a path $P$ in the dual graph of $G$, such that the first edge of $P$ crosses $S_1$, the last edge of $P$ crosses $S_3$, and the two components

<footnote n="4">⁴ Observe that the Tutte's spring embedding algorithm gives a solution, but with exponential grid size, and the two combinatorial algorithms mentioned in this chapter [CDF18b; GL14] yield periodic grid-drawings for toroidal triangulations having the aesthetic disadvantage that some edges are allowed to cross the boundary of the drawing.</footnote>
<figure><img src="image_90.png" /><figcaption>Figure 5.18: Example of execution of the shift algorithm on a half-4-scheme trian-
gulation H with 10 vertices. We use $I_0 = (2,2,2)$ as initial interspace vector on the
bottom path $S_1$.</figcaption></figure>

H, H' of G separated by P are H4ST (with S2 as bottom path of the left com-
ponent and S4 as bottom-path of the right component), see Fig. 5.17(top).
A straight-line drawing of a H4ST H is called *admissible* if S1 is horizontal,
S2 and S4 are vertical, and all edges in S3 have slope in {-1, 0, +1}. By an
extension of the shift paradigm underlying the FPP algorithm, Duncan et al.
show that it is possible to obtain an admissible straight-line drawing of H on
a grid of size O(n × n²), more precisely a grid of size O(n × (d + 1)n), where
n is the number of vertices of H and d is the graph-distance between S1 and
S3 (Fig. 5.18 illustrates the steps of this variation of the shift paradigm).

To obtain a straight-frame drawing of a 4ST G, decompose G along a
river between S₁ and S₃ into two H4ST components H and H', draw H and
H' using the shift algorithm (with S₂ as the bottom-path of H and S₄ as
the bottom-path of H'), and then shift the left boundary of the component
whose drawing has the smaller width so that the widths of the drawings of
H and H' coincide. Then rotate the drawing of H by π/2 clockwise, rotate the
drawing of H' by π/2 counterclockwise, and put the two drawing in front
of each other, leaving enough horizontal space between them so that the
edges connecting H to H' have slope smaller than 1 in absolute value. Since
the edges on the boundaries of (the rotated copies of) H and H' are either
vertical or of slope in {-1, +1}, the edges between H and H' do not introduce
crossings, so the resulting drawing of G is planar, see Fig. 5.17(bottom).
Overall the grid-size is O(n² × n), more precisely O(n(d+1) × n), with
d the graph-distance between S₂ and S₄.

<figure><img src="image_91.png" /><figcaption>Figure 5.17: Illustration of the algo-
rithm of Duncan et al. [DGK11] for
drawing a 4ST G (top). The river be-
tween S₁ and S₃ decomposes G into
two H4ST H, H' (shaded). (bottom)
The straight-frame drawing of G as
given in [DGK11], which results from
the two drawings of H, H' put to-
gether.</figcaption></figure>

5.4.2 Our modified version of the algorithm: aligning vertical coordinates

A first simple adaptation we do is to do all (abscissa) shift operations by 2
instead of doing them by 1. Given a H4ST G, let p be the number of edges
of S1. For a vector I of p even integers, I is called the *initial interspace vector*,
consider the shift algorithm for G starting with S1 drawn as a horizontal
line with interspaces given by I. Let F(I) = (f1, ..., fₚ) be the vector repre-
senting the interspaces between consecutive vertices on S1 at the end of the
algorithm; F(I) is called the *final interspace vector*. For our purpose, the advan-
tage of doing the shift operations by 2 is to guarantee that the components
of F(I) are even (see Fig. 5.18 for an example).

**Lemma 5.6** Let $F_0 = F(I_0)$ be the final interspace vector when using $I_0 = (2, 2, \dots, 2)$ as initial interspace vector on $S_1$. Then for any vector $F$ of $p$ even integers such that $F \ge F_0$ (component-wise), it is possible to re-execute the shift-algorithm so as to have $F$ as final interspace vector.
<figure><img src="image_92.png" /><figcaption>Figure 5.20: The top pictures illustrate our binary decomposition of a 4-scheme triangulation G (left), where we distinguish a chordless path P just below $S_3$ (shown bolder). Cutting along P yields two components: a 4-scheme triangulation B and a band-graph A which is further decomposed into 3 pieces L, M, R.</figcaption></figure>

<figure><img src="image_93.png" /><figcaption>Figure 5.19: Our modified version of the algorithm of Duncan et al. [DGK11] (with an oblique edge on $S_3$). The application of Lemma 5.7 (for $m = 2$) ensures that the ordinates of the vertices on the left vertical path $S_2$ coincide with the ordinates of the corresponding vertices on the right path $S_4$. The input 4-scheme triangulation corresponds to the example given in Fig. 5.17.</figcaption></figure>

### ALIGNING VERTICES ON $S_1$ AND $S_3$
We can now give another strategy (suited in view of showing Theorem 5.5) for drawing a 4ST G, while guaranteeing that some of the vertices on the opposite sides of the frame will have the same vertical coordinates. To be more precise the resulting drawing is not straight-frame, but is straight-frame except for an oblique edge along $S_3$, and is such that, with $m = \min(|S_2|, |S_4|)$, the $m$ first components of the interspace vectors along $S_2$ and $S_4$ (ordered from bottom to top) coincide (as illustrated in the example of Fig. 5.19).

At first, similarly as in [DGK11] we cut G along a river (between $S_1$ and $S_3$) into two components H and $H'$. Then we draw independently H and $H'$ using the shift algorithm (with width 2 strip insertions). Let $F_0$ ($F'_0$) be the final interspace vector of H (resp. of $H'$), starting with initial interspace vector $(2, \dots, 2)$. For $1 \le i \le m$ let $u_i$ be the maximum of the $i$th components of $F_0$ and $F'_0$. Because of the property stated in Lemma 5.6, one can redraw H and $H'$ so that the $m$ first components of the final interspace vectors of H and of $H'$ are $(u_1, \dots, u_m)$. In addition one can check that the widths of both drawings are at most $8n$, and the two widths differ by at most $4n$. Similarly as in [DGK11] we rotate H (resp. $H'$) by $\pi/2$ clockwise (resp. counterclockwise) and place the drawings in front of each other, leaving horizontal space $8n$ between them, enough to draw the edges between H and $H'$ crossing-free. We obtain (see Fig. 5.19):

**Lemma 5.7** For any 4ST G with $n$ vertices, and $m = \min(|S_2|, |S_4|)$, there is a straight-line drawing of G, where $S_2$ and $S_4$ are vertical with their interspace vectors equal at the $m$ first components, $S_1$ is horizontal, and $S_3$ is horizontal except for an oblique edge of slope in $[-1/2, 1/2]$. The grid size is $O(n^2 \times n)$, more precisely $O(n(d+1) \times n)$ with $d$ the graph-distance between $S_2$ and $S_4$, and the drawing can be computed in linear time.
### 5.4.3 A new binary decomposition for 4-scheme triangulations

We now introduce a new way to decompose a 4ST G into two components A, B, in such a way that proving Theorem 5.5 will reduce to drawing B using Lemma 5.7, and then drawing A using a certain fixed outer frame. A path P is said to be *just below* $S_3$ if P connects a vertex of $S_2$ to a vertex of $S_4$, all non-extremal vertices of P avoid $S_2 \cup S_3 \cup S_4$, and each vertex on P (including the extremities) has at least one neighbour on $S_3$.

**Lemma 5.8** Each 4ST G has a chordless path just below $S_3$.

Let P be a chordless path just below $S_3$. Cutting G along P yields two 4ST denoted A and B, with B below P and A above P. We draw B using Lemma 5.7. Then we have to draw A —which is called the *band-graph*— in such a way that the drawing obtained by pasting the drawing of B with the drawing of A yields a periodic drawing of G.

**DRAWING THE BAND-GRAPH A (ON A GIVEN FIXED FRAME).** To state the drawing result for A, we introduce the notion of *fixed frame*. Given a quasi-triangulation G, with C its outer cycle, a fixed frame $\kappa$ for G is a crossing-free drawing of C on a regular grid $w \times h$ ($w$ and $h$ are the width and height of the fixed frame). For $\gamma \ge 1$ the grid is *refined by factor $\gamma$* by replacing each unit cell by a $\gamma \times \gamma$ regular grid. We say that the factor $\gamma$ is *suitable* for the pair $(G, \kappa)$ if, after refining the grid of $\kappa$ by factor $\gamma$, G admits a straight-line drawing with $\kappa$ as the outer face contour of the drawing, see Fig. 5.21 for an example.

Next Lemma states that, up to increase the vertex resolution of a linear factor, we can always draw a band-graph within a prescribed fixed frame (where the bottom path consists of horizontal segments except for an oblique edge, as in the top picture of Figure 5.22).

**Lemma 5.9** For each $K \ge 1$ and any fixed frame $\kappa$ for A (A is the band-graph of G, which has $n$ vertices) of the form shown in the top drawing of Figure 5.22, there is $\gamma_0$ in $O(n \cdot \max(n, K))$ such that any even factor $\gamma \ge \gamma_0$ is suitable for (A, $\kappa$).

The validity of this statement, for drawing the band-graph A of a 4ST G with $n$ vertices obtained after cutting along a chordless path P, relies on a further chordal decomposition (see right pictures in Fig. 5.20).

Let $a$ be the extremity of P on $S_2$ and $b$ the extremity of P on $S_4$. Let $u_a$ be the leftmost neighbour of $a$ along $S_3$ and let $u_b$ be the rightmost neighbour of $b$ along $S_3$. Then cutting A along the edges $\{a, u_a\}$ and $\{b, u_b\}$ yields three pieces: a left-piece L, a middle piece M, and a right-piece R (as in Fig. 5.20). Note that L (and similarly R) is either empty (if $u_a$ is the top-left corner of G) or otherwise is naturally a 3-scheme triangulation, a quasi-triangulation with three corners are $a, u_a$ and the topleft corner of G: drawing L and R with a fixed frame requires a further decomposition along the chordal edges, if any, between the bottom and vertical paths as shown in the drawing of Fig. 5.23 (the details of the construction are omitted here and can be found in [CFK14]). Observe that M is naturally a 4ST such that $|S_2(M)| = |S_4(M)| = 1$ (so we can apply a variation of Lemma 5.7).

**FINAL STEP: COMPUTING THE PERIODIC STRAIGHT-FRAME DRAWING.**
We claim that Lemma 5.7 together with Lemma 5.9 imply Theorem 5.5 (at the moment with grid-size $O(n^5 \times n^5)$). Indeed, once B is drawn using Lemma 5.7, one easily designs a fixed frame of the form of Fig. 5.22 and

<figure><img src="image_94.png" /><figcaption>Figure 5.21: In order to draw a quasi-triangulation G in a fixed frame $\kappa$ (on a grid of size $4 \times 2$), we use a refinement factor 3 for the grid (hence the factor 3 is suitable for $(G, \kappa)$).</figcaption></figure>

<figure><img src="image_95.png" /><figcaption>Figure 5.22: Left: frame for the band-graph A, middle: frame for the middle piece M of A, right: frame for the left piece L of A.</figcaption></figure>
<figure><img src="image_96.png" /><figcaption>Figure 5.23: Chordal decomposition of a 3-scheme triangulation, with one side (hypotenuse) reduced to an edge.</figcaption></figure>

such that pasting a drawing of A in this frame with the drawing of B yields a periodic drawing of G (note that the lower part of $κ$ is determined by the property of fitting with the boundary-path $S_3(B)$, and the upper part of $κ$ is determined by the property of fitting with the boundary-path $S_1(B)$ in order to get the periodicity property). Note that the parameter K equals the width of the drawing of B, which is $O(n^2)$. Since the refinement factor for A is in $O(n \cdot \max(n, K))$, the grid-size of the resulting drawing of G is $O(K^2n \times K^2n)$, which is $O(n^5 \times n^5)$.

### 5.4.4 Final remarks

**DEALING WITH CHORDS BETWEEN BOUNDARY PATHS.** In order to carry out the decomposition of the input 4ST G based on the path just below $S_3$ we have assumed that there is no chord between $S_1$ and $S_3$. If there is a chord between $S_1$ and $S_3$ but there is no chord between $S_2$ and $S_4$, then we can just rotate G by $\pi/2$ (so as to exchange $S_1, S_3$ with $S_2, S_4$). If there is also a chord between $S_2$ and $S_4$ then it must be incident to a corner vertex: this case requires a slight modification of our construction (a more detailed discussion is provided in [CFK14]).

**IMPROVING THE GRID SIZE.** We would like to point out that in the case where there is no chord incident to a corner of G, then G actually admits a periodic straight-frame drawing of grid-size $O(n^4 \times n^4)$. This fact relies mainly on the following remark. Let us assume that the input 4-scheme triangulation G has $n$ vertices and there are no chords between boundary paths (let $d_h$ be the graph-distance between $S_1$ and $S_3$, and let $d_v$ be the graph-distance between $S_2$ and $S_4$). Then it follows from the Menger vertex-disjoint theorem and the fact that G is innerly triangulated that $d_h \times d_v \le n$, hence $\min(d_h, d_v) \le n^{1/2}$: this implies that, up to possibly rotating G by $\pi/2$ to ensure that $d_h \le d_v$, the Duncan et al. algorithm gives a grid-size $O(n \times n^{3/2})$ (instead of the worst case $O(n \times n^2)$ grid-size mentioned in Section 5.4.3). A few more technical arguments (omitted here) should be required to deal with case where there are chords between boundary paths.
## 5.5 SPHERICAL DRAWINGS OF PLANAR GRAPHS

The notion of planar drawings can be naturally generalized to the spherical case: the main difference is that edges are mapped to geodesic arcs on the unit sphere S², which are minor arcs of great circles (obtained as intersection of S² with a hyperplane passing through the origin). A geodesic drawing of a map should preserve the cyclic order of neighbors around each vertex (such an embedding is unique for triangulations, up to reflexions of the sphere). As in the planar case, we would aim to obtain crossing-free geodesic drawings, where geodesic arcs do not intersect (except at their extremities): these are referred to as spherical drawings. Sometimes, the weaker notion of spherical parameterization (an homeomorphism between an input mesh and S²) is considered for dealing with applications in the geometry processing domain (e.g. for dealing with mesh morphing): while the bijectivity between the mesh and S² is guaranteed, there are no guarantees that the triangle faces are mapped to spherical triangles with no overlaps (obviously a spherical drawing leads to a spherical parameterization).

### 5.5.1 Related works

#### Spherical parameterization via Tutte barycentric method (in the plane)

A simple solution to the spherical parameterization problem consists in planarizing the input graph and to apply the standard Tutte barycentric method (this can be done in several ways, as illustrated below): one main advantage is that one can preserve some of the aesthetic appeal of Tutte's planar drawings. The main drawback is that these maps are bijective but cannot produce in general a crossing-free spherical drawing (straight-line segments in the plane are not mapped to geodesics by inverse stereographic or polar-to-cartesian projections). Nevertheless, the methods based on planarization are extremely simple to implement (and rather efficient in practice) and can be used as initial placers for more sophisticated iterative spherical layout algorithms (an experimental evaluation will be provided in Section 5.6).

**INVERSE STEREO PROJECTION LAYOUT (isp).** The solution suggested by Saba et al. [Sab+05] (see Fig. 5.24) consists in partitioning the input graph G into two components homeomorphic to a disk: this is achieved by computing a small simple cycle separator (having $O(\sqrt{n})$ vertices) whose removal produces a balanced partition ($G^S, G^N$) of the faces of G. The two graphs $G^S$ and $G^N$ are then drawn in the plane using Tutte's barycentric method: boundary vertices lying on the separator are mapped on the unit disk. Combining a Moebius inversion with the inverse of a stereographic projection we obtain a spherical parameterization of the input graph.

**POLAR-TO-CARTESIAN LAYOUT (pc).** The approach adopted in Zayer, Rössl, and Seidel [ZRS06] relies on a different planarization step (the result is shown in Fig. 5.25): the edges along a simple path from a south pole $v^S$ to a north pole $v^N$. A planar rectangular layout is computed by applying Tutte parameterization with respect to the azimuthal angle $\theta \in (0, 2\pi)$ and to the polar angle $\phi \in [0, \pi]$.

<figure><img src="image_97.png" /><figcaption>Figure 5.24: A spherical parameterization of the gourd graph obtained combining a Tutte's planar parameterization with an inverse stereo projection.</figcaption></figure>

<figure><img src="image_98.png" /><figcaption>Figure 5.25: A spherical parameterization of the gourd graph obtained via Tutte's planar parameterization.</figcaption></figure>
Tutte barycentric embedding and force-directed layouts on the sphere

**ITERATIVE RELAXATION: PROJECTED GAUSS-SEIDEL.** The first method can be viewed as an adaptation of the iterative scheme solving Tutte equations. This scheme consists in moving points on the sphere in tangential direction in order to minimize the spring energy (its pseudo-code is shown in Fig. 5.26)

$$ \epsilon = \frac{1}{2} \sum_{i=1}^{n} \sum_{j \in N(i)} w_{ij} \|\mathbf{x}(v_i) - \mathbf{x}(v_j)\|^2 \quad (5.1) $$

with the only constraint $||\mathbf{x}(v_i)|| = 1$ for $i = 1...n$ (in our implementations we use uniform weights $w_{ij}$, as in Tutte's work). As opposed to the planar case, there are no boundary constraints on the sphere, which makes the resulting layouts collapse in many cases to degenerate solutions. As observed in [GGS03; Sab+05] this method does not always converge to a valid spherical drawing, and its practical performance strongly depends on the geometry of the starting initial layout $\mathbf{x}^0$. While not having theoretical guarantees, this method is quite fast allowing to quickly decrease the residual error: it thus can be used in a first phase and combined with more stable iterative schemes leading in practice to better convergence results [Sab+05] (still lacking of rigorous theoretical guarantees).

**ALEXA'S METHOD.** In order to avoid the collapse of the layout, without using artificial constraints, Alexa [Aleoo] modified the iterative relaxation above by penalizing long edges (tending to move vertices in a same hemisphere). More precisely, the vertex $v_i$ is moved according to a displacement $\Delta_i = c \frac{1}{\deg(v_i)} \sum_j (\mathbf{x}(v_i) - \mathbf{x}(v_j)) ||\mathbf{x}(v_i) - \mathbf{x}(v_j)||$ and then reprojected on the sphere. The parameter c regulates the step length, and can be chosen to be proportional to the inverse of the longest edge incident to a vertex, improving the convergence speed.

**FORCE-DIRECTED LAYOUTS ON THE SPHERE.** While spring embedders are originally designed to produce 2D or 3D layouts, one can adapt them to spherical geometry. We have implemented the standard spring-electrical model introduced in [FR91] (referred to as FR), and its spherical version 5 following the framework described by Kobourov and Wampler [KW05] (called Spherical FR). As in [FR91] we compute attractive forces (between adjacent vertices) and repulsive forces (for any pair of vertices) acting on vertex u, defined by:

$$ F_a(u) = \sum_{(u,v) \in E} \frac{\|\mathbf{x}(u) - \mathbf{x}(v)\|}{K} (\mathbf{x}(u) - \mathbf{x}(v)), \quad F_r(u) = \sum_{v \in V, v \neq u} \frac{-CK^2(\mathbf{x}(v) - \mathbf{x}(u))}{\|\mathbf{x}(u) - \mathbf{x}(v)\|^2} $$

where the values C (the strength of the forces) and K (the optimal distance) are scale parameters. When implementing the spherical version, we must pay attention to some details: for instance we shift the repulsive forces by a constant term, making the force acting on pairs of antipodal vertices zero.

<figure><img src="image_99.png" /><figcaption>Figure 5.26: The pseudo-code of the Projected Gauss-Seidel method.</figcaption></figure>

<figure><img src="image_100.png" /><figcaption>Figure 5.27: Using iterative solvers the drawing can sometimes collapses to degenerate layouts.</figcaption></figure>
<figure><img src="image_101.png" /><figcaption>3 disjoint paths 3 rivers</figcaption></figure>

<caption>Figure 5.28: Computation of a spherical drawing based on a prism layout of the gourd graph (326 vertices). Three vertex-disjoint chord-free paths lead to the partition of the faces of G into three narrow 4-scheme triangulations $G_0^C$, $G_1^C$ and $G_2^C$ which are each separated by one river (green faces). Once the three planar layouts are computed (refer to Fig. 5.29) we can glue together the identified sides and obtain a 3D prism $M$: its central projection on the sphere produces a spherical drawing.</caption>

## 5.6 OUR CONTRIBUTION: A FAST SPHERICAL DRAWING WITH THEORETICAL GUARANTEES

We now provide an overview of our algorithm for computing a spherical drawing of a planar triangulation $\mathcal{T}$ in linear time, called SFPP layout (see Fig. 5.28 for an illustration). Our solution relies on the results sketched in Section 5.4: more precisely, we apply our two-pass implementation of the shift paradigm, described in Section 5.4.2, which allows us to obtain a straight-frame drawings with vertices aligned on opposite sides. A more detailed presentation can be found in [CDF18a].

**STEP 1: MESH SEGMENTATION.** Assuming that there are two non-adjacent faces $f^N$ and $f^S$ (with no common incident vertices $^6$), one can compute in linear time $^7$ 3 disjoint and chord-free paths $P_0, P_1$ and $P_2$ from $f^S$ to $f^N$. Denote by $u_0^N, u_1^N$ and $u_2^N$ the three vertices of $f^N$ on $P_0, P_1$ and $P_2$ (define similarly the three neighbors $u_0^S, u_1^S, u_2^S$ of the face $f^S$). We first compute a partition of the faces of $\mathcal{T}$ into 3 4-scheme triangulations, denoted by $G_0^C, G_1^C$ and $G_2^C$, cutting $\mathcal{T}$ along the paths above and removing $f^S$ and $f^N$. The first pair of opposite sides only consist of an edge (drawn as vertical segment in Fig. 5.29), while the remaining pair of opposite sides contains vertices lying on $P_i$ and $P_{i+1}$ respectively (indices being modulo 3): according to these definitions, $G_i^C$ and $G_{i+1}^C$ share the vertices lying on $P_{i+1}$ (drawn as a path of horizontal segments in Fig. 5.29).

Note that $\mathcal{T}$ can be seen as a *prism* (as illustrated in Fig. 5.28), with $f^N$ and $f^S$ as the two triangular faces and with $G_0^C, G_1^C$ and $G_2^C$ occupying the three lateral quadrangular faces of the prism.

<footnote n="5">5 The experimental evaluation of our implementation of Spherical FR method is given in Section 5.7</footnote>

<footnote n="6">6 If this is not the case, one can force the existence of two such faces by adding a new triangle $t$ within a face (and adding edges so as to triangulate the area between $t$ and the face-contour)</footnote>

<footnote n="7">7 Once again Schnyder woods provide a nice and efficient way for computing paths $P_i$. Taking $f^N$ as the outer face, where $v_0, v_1, v_2$ are the outer vertices in clockwise (CW) order and inserting a vertex $v$ of degree 3 inside $f^S$, we compute a Schnyder wood of the resulting triangulation. Let $P_0, P_1, P_2$ be the directed paths in respective colors 0, 1, 2 starting from $v$: the well-known properties of Schnyder woods ensure that these paths are chord-free and disjoint except at $v$, ending at the 3 vertices $v_0, v_1, v_2$ of $f$. Deleting $v$ and its 3 incident edges, (and thus deleting the starting edge in each of $P_0, P_1, P_2$) we obtain a triple of disjoint chord-free paths from $f^S$ to $f^N$. Let $u_0, u_1, u_2$ be the vertices on $f^S$ incident to $P_0, P_1, P_2$.</footnote>
<figure><img src="image_102.png" /><figcaption>Figure 5.29: Our variant of the FPP algorithm allows to produce straight-frame layouts of the three 4-scheme triangulations $G_0^C$, $G_1^C$ and $G_2^C$, where boundary vertex locations do match on identified horizontal sides (corresponding to the common path $P_{i+1}$) shared by $G_i^C$ and $G_{i+1}^C$).</figcaption></figure>

**STEP 2: COMPATIBLE DRAWINGS OF RECTANGULAR FRAMES.** We apply the strategy sketched in Section 5.4 to obtain three rectangular layouts of $G_0^C$, $G_1^C$ and $G_2^C$ (as illustrated in Fig. 5.29): this algorithm first separates each $G_i^C$ into two sub-graphs by removing the so-called river (an outer-planar graph consisting of a face-connected set of triangles which corresponds to a simple path in the dual graph, starting at $f^S$ and going toward $f^N$). The two-subgraphs of $G_i^C$ (bottom and top white regions in Fig. 5.29) are then processed making use of the *canonical labeling* defined in [DGK11]: the resulting layouts are stretched in order to fit into a rectangular frame (observe that after this first pass the boundary vertices corresponding to the path $P_i$ are not aligned). Just observe that in our case a pair of opposite sides only consists of two edges (vertical edges in Fig. 5.29), which leads to an algorithm considerably simpler to implement in practice. Finally, before re-inserting the set of edges in the river, we apply a two-phases adaptation of the shift algorithm similar to the one described in Section 5.4.2 to obtain a planar grid drawing of each 4-scheme triangulation $G_i^C$, such that the positions of vertices on the path $P_{i+1}$ in $G_i^C$ do match the positions of corresponding vertices on $P_{i+1}$ in $G_{i+1}^C$.

**STEP 3: SPHERICAL LAYOUT.** To conclude, we glue together the drawings of $G_0^C$, $G_1^C$ and $G_2^C$ computed above in order to obtain a drawing of $\mathcal{T}$ on a triangular prism. By a translation within the 3D ambient space we can make the origin coincides with the center of mass of the prism (upon seeing it as a solid polyhedron). Then a central projection from the origin maps each vertex on the prism to a point on the sphere: each edge $(u, v)$ is mapped to a geodesic arc, obtained by intersecting the sphere with the plane passing trough the origin and the segment relying $u$ and $v$ on the prism (crossings are forbidden since the map is bijective).

Note that the prism has its 3 lateral faces $G_i^C$ of area $O(n) \times O(n)$: this is implied by the resolution achieved by the algorithm of Duncan et. al [DGK11] and on the fact that the two opposite sides $(u_i^N, \dots, u_i^S)$ and $(u_{i+1}^N, \dots, u_{i+1}^S)$ of $G_i^C$ are at distance 1.

**Theorem 5.10 ([CDF18a])** Let $\mathcal{T}$ be a planar triangulation of size $n$, having two non-adjacent faces $f$ and $f'$. Then one can compute in $O(n)$ time a spherical drawing of $\mathcal{T}$, where edges are drawn as (non-crossing) geodesic arcs of length $\Omega(\frac{1}{n})$.

It is worth noting that the algorithmic tools involved in the theorem above are reasonable simple to combine, leading to an extremely fast implementation (see Section 5.7).

## 5.7 EXPERIMENTAL RESULTS

### 5.7.1 Spherical drawings

Here we provide an experimental evaluation of the combinatorial tools developed in the previous section for computing spherical drawings $^8$.

While the resulting SFPP layouts are rather unpleasing (as for the planar FPP algorithm), our solution is able to compute spherical drawings that are

<footnote n="8">8 The experimental results of this section are taken from [CDF18a].</footnote>
<figure><img src="image_103.png" /><figcaption>Figure 5.30: Spherical layouts of a random triangulation with 1K faces. While the projected Gauss-Seidel relaxation always collapses, Alexa method is more robust, but also fails when starting from a random initial layout. When using the ISP, PC or our SFPP layouts Alexa method converges toward a crossing-free layout: starting from the SFPP layout allows getting the same aesthetic criteria as the ISP or the PC layouts (with even less iterations). Spring embedders [FK12] (Spherical FR) prevent from reaching a degenerate configuration, but have some difficulties to unfold the layout.</figcaption></figure>

good starting points for both iterative methods and spring embedders: our intuition is that an initial layout which is crossing-free could be of some help to unfold the graph in order to obtain nicer spherical drawings, in a more efficient and robust way, as confirmed empirically by the experiments presented below.

**COMPARISON OF RUNNING TIMES.** The plots of Fig. 5.31 clearly show that our SFPP algorithm has an asymptotic linear-time behavior and in practice is much faster than the ISP and PC methods based on the resolution of linear systems, for which we use the conjugate solver of the MTJ library. Observe that a slightly better performance can be achieved with more sophisticated schemes or tools (e.g. Matlab solvers) as done in [AL15; Sab+05]. Nevertheless the timing cost still remains much larger than ours: as reported in [AL15] the parameterization of the Dragon graph (655k vertices) requires 19 seconds for solving the linear systems (on a 3.5GHz Intel i7 CPU), while the computation of our SFPP layout requires less than 1.2 seconds.

**QUANTITATIVE EVALUATION OF AESTHETIC CRITERIA.** In order to obtain a quantitative evaluation of the layout quality we compute the spring

<figure><img src="image_104.png" /><figcaption>Figure 5.31: (top) Runtime costs for the computation of our SFPP layouts. (bottom) Timing cost for solving the linear systems for the ISP and PC layouts (we use the MTJ conjugate gradient solver with a numeric tolerance of $10^{-6}$). All results are expressed in seconds.</figcaption></figure>
<figure><img src="image_105.png" /><figcaption>Figure 5.32: Comparison of spherical layouts of a random triangulation with 1K faces: we evaluate the performances of Alexa method, starting from several initial layouts. The charts above show the plot of the energy, edge lengths and areas statistics computed when running 800 iterations of Alexa method (we compute these statistics every 10 iterations).</figcaption></figure>

energy $\epsilon$ defined by Eq. 5.1 and two metrics measuring the edge lengths and the triangle areas (refer to the plots of Fig. 5.32). As suggested in [FK12] we compute the average percent deviation of edge lengths, according to

$$ \epsilon_l := 1 - \left( \frac{1}{|E|} \sum_{e \in E} \frac{|l_g(e) - l_{\text{avg}}|}{\max(l_{\text{avg}}, l_{\text{max}} - l_{\text{avg}})} \right) \qquad (5.2) $$

where $l_g(e)$ denotes the geodesic distance of the edge $e$, and $l_{\text{avg}}$ (resp. $l_{\text{max}}$) is the average geodesic edge length (resp. maximal geodesic edge length) in the layout. Similarly we compute the average percent deviation of triangle areas, denoted by $\alpha$. The metrics $\epsilon_l$ and $\alpha$ take values in $[0...1]$, and higher values indicate more uniform edge lengths and triangle areas<fnref n="9" />.

### Comparisons of layouts

We evaluate and compare the spherical layouts obtained applying iterative schemes (Alexa's method, projected Gauss-Seidel scheme and the Spherical FR force-directed embedder), when starting from distinct initial layouts (initial random locations, ISP, PC and our SFPP).

All our tests confirm that starting with random vertex locations is almost always a bad choice, since iterative methods lead in most cases to a collapse before reaching a valid spherical drawing (spherical spring embedders do not have this problem, but cannot always eliminate edge crossings, see Fig. 5.30). Our experiments (see Fig. 5.30) also confirm a well known fact: Alexa's method is more robust compared to the projected Gauss-Seidel relaxation, leading almost always to a valid configuration without collapsing (more tests and statistics, also including real-world 3D meshes, can be found in [CDF18a]).

### LAYOUT OF RANDOM TRIANGULATIONS.
When drawing random triangulations the performances obtained starting from our SFPP layout are often better than the ones achieved using the ISP layout (and similar to the ones of the PC layout). As illustrated by the pictures in Fig. 5.30 and 5.34, Alexa's method is able to reach a non-crossing configuration requiring less iterations when using our SFPP layout instead of ISP layout: this is observed in most of our experiments, and clearly confirmed by the plots of the energy and statistics $\epsilon_l$ and $\alpha$ that converge faster to the values of the final layout (see charts in Fig. 5.32).

### 5.7.2 Spherical preprocessing for Euclidean spring embedders

We investigate the use of spherical drawings as initial placers for spring embedders in 3D space. The fact of recovering the original topological shape of the graph, at least in the case of graphs that have a clear underlying geometric structure, is an important and well known ability of spring embedders. This occurs for the case of regular graphs used in Geometry Processing (the pictures in Fig. 5.33 show a few force-directed layouts of the cow graph), but also for the case of random maps, for which spring embedding algorithms (applied in the 3D ambient space) yield graph layouts that greatly capture the topological and structural features of the map (the genus of the surface is visible, the "central charge" of the model is reflected by the presence of

<footnote n="9">⁹ Observe that one common metric considered in the geometric processing community is the (angle) distortion: in our case this metric cannot be taken into account since our input is a combinatorial structure (without any geometric embedding).</footnote>
<figure><img src="image_106.png" /><figcaption>Figure 5.33: Use of spherical drawings as initial placers for force-directed methods: we compute the layouts of the cow graph (2904 vertices, 5804 faces) using our 3D implementation of the FR spring embedder [FR91]. Starting from a good initial shape helps to untangle faster the graph, leading very often to better local minima. A quantitative confirmation is provided by the plots in Fig. 5.35.</figcaption></figure>

<figure><img src="image_107.png" /><figcaption>Figure 5.34: Force-directed drawings of a random planar triangulation with 5K faces: spherical drawings are used as initial placers for the 3D version of the FR spring embedder [FR91].</figcaption></figure>

spikes, etc.)<fnref n="10" />. While common software and libraries for graph visualization (e.g. GraphViz [Ell+01], Gephi [BHJ09], GraphStream) provide implementations of many force-directed models, as far as we know they never try to exploit the strong combinatorial structure of surface-like graphs.

DISCUSSION OF EXPERIMENTAL RESULTS. Our main goal is to show empirically that starting from a nice initial shape that captures the topological structure of the input graph greatly improves the convergence speed and layout quality. In our experiments (see Figures 5.33 and 5.34) we run

<figure><img src="image_108.png" /><figcaption>Figure 5.35: 3D FR layout of the cow graph (2904 vertices) obtained starting from the two different initial placements drawn in Fig. 5.33. We plot the number of colliding 3D triangles, over 100 iterations of the FR</figcaption></figure>

<footnote n="10">10 A great variety of such representations can be seen at the very nice simulation gallery of Jérémie Bettinelli (http://www.normalesup.org/~bettinel/simul.html).</footnote>
<figure><img src="image_109.png" /></figure>

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

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

Figure 5.36: 3D layout of a random planar triangulation with 5K faces: spherical drawings are used as initial placers for the 3D version of the FR spring embedder [FR91]. We plot the number of colliding 3D triangles, over 100 iterations of the FR algorithm.

our 3D implementation of the spring electrical model FR [FR91]<fnref n="11" /> starting from several distinct initial layouts.

In order to quantify the layout quality, we evaluate the number of self-intersections of the resulting 3D shape during the iterative computation process<fnref n="12" />. To be more precise, we plot over the first 100 iterations the number of triangle faces that have a collision with a non adjacent triangle in 3D space (see charts of Fig. 5.35 and 5.36).

Our experiments clearly confirm the visual intuition suggested by pictures: when starting from a good initial shape the force-directed layouts seem to evolve according to an inflating process, which leads to better and faster untangle the graph layout. This phenomenon is observed in all our tests (on several mesh-like graphs and synthetic data): experimental evidence shows that an initial spherical drawing is a good starting point helping the spring embedder to reach nicer layout aesthetics and also to improve the runtime performances. Finally observe that from the computational point of view the computation of a spherical drawing has a negligible cost: iterative schemes (e.g. Alexa method) require O(n) time per iteration, which must be compared to the complexity cost of force-directed methods, requiring between O(n²) or O(n log n) time per iteration (depending on the repulsive force calculation scheme).

<footnote n="11">11 In our implementation of the FR algorithm we make use of exact force computation and we adopt the cooling system proposed in [Walo3] (with repulsive strength $C = 0.1$).</footnote>

<footnote n="12">12 We compute the intersections between all pairs of non adjacent triangles running a brute-force algorithm: the runtimes reported in Fig. 5.33 and 5.34 do not count the cost of computing the triangle collisions.</footnote>
In this section we provide some experimental results<fnref n="1" /> involving both planar and higher genus Schnyder woods: in particular we wrote a Java program that performs an exhaustive generation of all possible 3-orientations and Schnyder woods for surfaces of low genus. In the case of tiny triangulations (having at most a few tens of vertices) our generator is fast enough to list all distinct Schnyder woods in a reasonable amount of time (up to a few hours): this allows us to compute some statistics and test some conjectures.

## 6.1 EXPERIMENTAL RESULTS ON HIGHER GENUS SCHNYDER WOODS

The results presented in this section are obtained running our Schnyder wood generator on all simple triangulations of genus 1 and 2. All distinct triangulations can be generated using the `surftri` tool developed by Thom Sulanke [Sul17; SL09] which produces the collection of all triangulations of a surface (up to a given size) starting from the set of *irreducible triangulations* of that surface. Table 6.1 reports the enumeration of triangulations of the torus and the double torus for $n \le 11$.

**MONOCHROMATIC CYCLES IN TOROIDAL SCHNYDER WOODS.** For each tiny toroidal triangulation, we have computed all distinct 3-orientations corresponding to toroidal Schnyder woods that satisfy the local condition (T1): then we have checked whether there exists a Schnyder wood for which the edges of the same color define a connected graph (having thus 3 monochromatic cycles, one for each color). According to our experiments, this is true for all simple toroidal triangulations with at most 11 vertices, providing a partial empirical confirmation to an open question stated in [GL14].

**SCHNYDER WOODS FOR THE DOUBLE TORUS.** It is known that any simple triangulation of genus $g \ge 1$ admits an edge orientation such that for every vertex the outdegree is divisible by 3 and at least 3 (this result, proved by Albar, Gonçalves, and Knauer [AGK16], confirms a conjecture of Barât and Thomassen [BTo6]). As already mentioned, already for $g = 1$ there are 3-orientations that do not correspond to Schnyder woods (recall the example of Fig. 3.1): but Theorem 3.10 ensures that any toroidal triangulation admits a Schnyder wood (so, there is at least one 3-orientation whose corresponding edge coloring satisfies the (T1) condition of Definition 3.9). For $g \ge 2$ a similar question naturally arises: one could ask whether it would be always possible to find a 3-orientation as defined above (the outdegree is a multiple of 3 and there are no sinks) that yields an edge coloring for which every vertex satisfies a *multiple* local Schnyder condition, as depicted in Fig. 6.2. This question was open until very recently: as shown in its PhD dissertation by Jason Suagee [Sua21], we now know that any simple triangulation of genus $g \ge 1$ having edge-width at least $40(2^9 - 1)$ admits such a kind of Schnyder wood.

<table><thead><tr><th>n</th><th># irreducible triangulations</th><th>#triangulations (g = 1)</th></tr></thead><tbody><tr><td>7</td><td>1</td><td>1</td></tr><tr><td>8</td><td>4</td><td>7</td></tr><tr><td>9</td><td>15</td><td>112</td></tr><tr><td>10</td><td>1</td><td>2109</td></tr><tr><td>11</td><td>—</td><td>37867</td></tr></tbody></table>

<table><caption>Figure 6.1: Number of simple triangulations of genus 1 and 2 (results are obtained using `surftri`).</caption><thead><tr><th>n</th><th># irreducible triangulations</th><th>#triangulations (g = 2)</th></tr></thead><tbody><tr><td>7</td><td>—</td><td>—</td></tr><tr><td>8</td><td>—</td><td>—</td></tr><tr><td>9</td><td>—</td><td>—</td></tr><tr><td>10</td><td>865</td><td>865</td></tr><tr><td>11</td><td>26276</td><td>113506</td></tr></tbody></table>

A triangulation is irreducible if there is no contractible edge.

<figure><img src="image_112.png" /><figcaption>Figure 6.2: Multiple local Schnyder condition: the outdegree of every vertex is a positive multiple of 3.</figcaption></figure>

<footnote n="1">¹ Many experimental results presented in this chapter (Sections 6.2, 6.3 and 6.4) are taken from [Cas19].</footnote>
<figure><img src="image_113.png" /><figcaption>Figure 6.3: Three Schnyder woods of the same portion of a spherical grid (the whole mesh is shown in Fig. 6.4): our heuristic leads to a majority of balanced vertices (white circles), while the minimal Schnyder wood is strongly unbalanced.</figcaption></figure>

Our experiments give an empirical confirmation of this result and suggest that the assumption on the edge-width is maybe unnecessary. We generated all possible 3-orientations (defined as above) for all distinct simple triangulations of genus 2 with at most 11 vertices, and checked the local Schnyder condition at every vertex. As we observed, for any such triangulation there exists a generalized Schnyder wood satisfying the multiple Schnyder condition of Fig. 6.2, with no restriction on the edge-width.

## 6.2 BALANCE OF PLANAR SCHNYDER WOODS

**MOTIVATION.** The main idea motivating the experiments of this section is that, in practice, most real-word graphs exhibit strong regularities which make them far from the random and pathological cases. Based on this remark, we want to explore the possibility to exploit this regularity in order to obtain better results for algorithmic problems involving Schnyder woods. As far as we know, the problem of providing an adaptive analysis of Schnyder woods taking into account the graph regularity has not been investigated so far: in particular our goal is to evaluate the role of balanced Schnyder woods (where, intuitively, the number of incoming edges of each color at inner vertices is more or less the same). Here we provide empirical evidence about the fact that balanced Schnyder woods can lead to fast solutions achieving good results in practice, especially for real-world graphs: as test applications, we evaluate the layout quality of a Schnyder drawings (Section 6.3) and we consider the problem of computing small separators for planar graphs (Section 6.4).

**MEASURING THE BALANCE.** The first step is to provide some notion of measure of the balance of a Schnyder wood: given an inner vertex v of degree $deg(v)$ having $\text{indeg}_i(v)$ incoming edges of color i (for $i \in \{0, 1, 2\}$), we define its *defect* as $\delta(v) = \max_i \text{indeg}_i(v) - \min_i \text{indeg}_i(v)$ if $deg(v)$ is a multiple of 3, and $\delta(v) = \max_i \text{indeg}_i(v) - \min_i \text{indeg}_i(v) - 1$ otherwise (refer to Fig. 6.5 for an illustration). We say that a vertex is *balanced* if $\delta(v) = 0$ and a Schnyder wood is *well balanced* if a majority of vertices have a small defect. Another interesting parameter, closely related to the defect defined above, is the number of 3-colored faces $^2$. For regular graphs is possible, in principle, to get a Schnyder wood that is perfectly balanced: $\delta(v) = 0$ almost everywhere and most faces are 3-colored, as shown in Fig. 6.3(left). In practice many Schnyder woods are unbalanced and we are not aware of existing theoretical or empirical results on the balance of Schnyder woods.

Unfortunately, we cannot check the existence of Schnyder woods for triangulations embedded on surfaces of genus $g \ge 3$: in order to run the *surftri* tool one needs the list of all irreducible triangulations of genus 3 and such a list is not provided with the *surftri* tool.

<figure><img src="image_114.png" /><figcaption>Figure 6.4: A spherical triangulation endowed with a well balanced Schnyder wood.</figcaption></figure>

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

<figure><img src="image_116.png" /><figcaption>Figure 6.5: Balanced vertices have defect $\delta = 0$.</figcaption></figure>

<footnote n="2">2. Observe that there are a number of interesting results on Schnyder woods involving the number of 3-colored faces (refer to [Bono2] for more details).</footnote>
<figure><img src="image_117.png" /><figcaption>Figure 6.6: Example of execution of our heuristic algorithm for the computation of a well balanced Schnyder wood. The pseudo-code is given in Fig. 6.7.</figcaption></figure>

### 6.2.1 Our heuristic for well balanced Schnyder woods

Observe that the vertex shelling procedure for computing Schnyder woods and canonical ordering (Section 2.2) has many degrees of freedom: at each step the choice of the vertex to be removed can possibly lead to a different Schnyder wood. In order to get as much as possible balanced vertices, we retard the removal of some vertices according to a balance priority (an example of execution of our heuristic is illustrated in Fig. 6.6). At a given step of the shelling procedure, we define the *priority* of a vertex $v$ as the total number incoming incident edges that already have been assigned a color and orientation (toward $v$).

Then we make use of very simple (truncated) priority rule: among the free vertices on the outer cycle B (the boundary of the outer face) we select one with maximal priority to be removed. If there are several boundary free vertices with the same priority, we remove the oldest vertex (the one that was added first to the cycle B). Intuitively, the goal of this approach is to retard the conquest of vertices having a small number of ingoing edges: observe that removing a vertex $v$ having 0 ingoing edges leads to get $d-3$ edges of color 2 ingoing at $v$, while the number of ingoing edges of colors 0 and 1 would remain 0 (thus $v$ would be unbalanced when its degree is greater than 4). From the implementation point of view, we use a collection of $k$ queues $Q_0, Q_2, \dots, Q_{k-1}$ (where $k$ is a small constant), to store the vertices according to their priorities (the priority of vertices is stored and maintained using an integer array $P$ of size $n$).

At the beginning of execution $Q_0$ contains only the outer vertex $V_2$ and the remaining queues are empty. When performing the vertex conquest of a free vertex $v$ on B we add to $Q_0$ the neighboring vertices that are discovered (getting an outgoing black edge), while we increase the priority of $v_l$ and $v_r$, the two left and right neighboring vertices of $v$, since they receive a new incoming edge (of color 0 and 1 respectively). We then add $v_l$ and $v_r$ at the
<figure><img src="image_118.png" /></figure>

<table><caption>Figure 6.8: The table above reports some statistics for tiny triangulations: the proportion of degree 6 vertices, the maximum vertex degree and the number $t_s$ of separating triangles. Last column reports the number $|S(T)|$ of all distinct Schnyder woods of a given rooted triangulation.</caption><thead><tr><th>Tiny graphs</th><th>n</th><th>|F|</th><th>d<sub>6</sub></th><th>d<sub>max</sub></th><th>t<sub>s</sub></th><th>|S(T)|</th></tr></thead><tbody><tr><td>globe5</td><td>27</td><td>50</td><td>0.55</td><td>6</td><td>0</td><td>5084208</td></tr><tr><td>random</td><td>28</td><td>52</td><td>0.17</td><td>17</td><td>7</td><td>1294</td></tr><tr><td>Finger</td><td>28</td><td>52</td><td>0.21</td><td>8</td><td>2</td><td>38760</td></tr><tr><td>delaunay</td><td>28</td><td>52</td><td>0.32</td><td>8</td><td>0</td><td>9355294</td></tr><tr><td>trigrid4</td><td>28</td><td>52</td><td>0.32</td><td>11</td><td>0</td><td>6953685</td></tr><tr><td>Hilbert</td><td>32</td><td>60</td><td>0.18</td><td>8</td><td>1</td><td>177903</td></tr><tr><td>Desk</td><td>34</td><td>64</td><td>0.23</td><td>8</td><td>5</td><td>199281</td></tr><tr><td>Lace</td><td>34</td><td>64</td><td>0.58</td><td>15</td><td>2</td><td>8843508</td></tr></tbody></table>

balancedSchnyderWood(T, (V₀, V₁, V₂), k)
B = {V₀, V₁, V₂} // initialization
T = new int[n] // priority array
Q₀ = ∅, Q₁ = ∅, ..., Qₖ₋₁ = ∅ // queue initialization
Q₀.addLast(v₂)
while(|B| ≠ {V₀, V₁}) {
  let M be the largest index s.t. Qₘ ≠ ∅
  let v = Qₘ.poll()
  if(v ∈ B and v is free) {
    let {vᵢ, vⱼ, ..., vₖ, vₖ} be the neighbors of v on B
colorOrient(v)
conquer(v) // remove v from B
T[vᵢ] += +, T[vⱼ] += ++ // increase priority
Qₘmax(k₋₁, T[vᵢ]).addLast(vᵢ)
Qₘmax(k₋₁, T[vⱼ]).addLast(vⱼ)
Q₀.addLast(vⱼ₁); ..., Q₀.addLast(vₖ)
}
}

<caption>Figure 6.7: Pseudo-code of the procedure for computing well balanced Schnyder woods.</caption>

end of $Q_P[v_1]$ and $Q_P[v_r]$ respectively. We do not increase the priority of a vertex having priority $k-1$ (thus having $k-1$ ingoing edges): the vertex is added to the end of $Q_{k-1}$. Observe that each vertex is added exactly once to $Q_0$, and can appear at most in $Q_0, Q_1, Q_2, \dots, Q_r$, where $r = \min(k-1, \deg(v)-3)$, since we have $k$ queues, and a vertex receives $\deg(v)$ incoming edges. At a given iteration of the incremental conquest, in order to choose a vertex candidate to be removed, we look for the largest index $M$ for which $Q_M$ is not empty: we remove the first vertex $u$ from the front of $Q_M$ and we check whether $u$ is still on $B$ and free (no incident chords), and we perform a `colorOrient` operation if this is the case.

**RUNTIME PERFORMANCES.** Our heuristic is very simple to implement and its linear-time behavior is confirmed by our experiments (where we set $k=5$): the computation of balanced Schnyder woods is slightly slower than the computation of minimal Schnyder woods, but it is still extremely fast in practice, allowing us to process more than 3M vertices per second (on both real-world and synthetic triangulations).

**POST-PROCESSING OPTIMIZATION: IMPROVING THE BALANCE.** The balance of the Schnyder woods obtained via our heuristic can be further improved by performing the reversal of oriented triangles. To be more precise, one can iterate over all (cw or ccw) oriented triangle faces and check whether the reversal of the orientation leads to increase the number of balanced vertices incident to the triangle: if this occurs the reversal is performed leading to a Schnyder wood with slightly larger number of balanced vertices. As illustrated by the charts in Figures 6.9 and 6.10, the improvement one can achieve with this post-processing phase is rather important for regular graphs: in our experiments we observed that the proportion of balanced vertices (denoted $\delta_0$) has increased between 14% and 88% on the tested meshes. The improvement is negligible for irregular (random) graphs. Unfortunately this post-processing phase is quite expensive: according to our experiments, iterating over the faces and reversing oriented triangles can be even 5.5 slower than running our heuristic.
<figure><img src="image_119.png" /><figcaption>Figure 6.9: Balance of tiny graphs. Graphs are listed from left to right according to the increasing values of $d_6$ (most regular graphs are listed rightmost). Whisker plots (blue) represent the entire ranges of computed values for a given parameter over all distinct Schnyder woods.</figcaption></figure>

### 6.2.2 *Experimental evaluation*

**TINY GRAPHS.** We consider tiny triangulations having less than 40 vertices, including both real-world and synthetic graphs (they are listed in Table 6.8): they are small enough so that we can generate all distinct Schnyder woods in a reasonable amount of time (a few hours) and compute some statistics involving their balance. More precisely, for a given rooted triangulation we compute all distinct Schnyder woods and plot three parameters (see charts in Fig. 6.9): the proportion $\delta_0$ of balanced vertices, the average vertex defect $\delta_{avg}$ and the proportion $\Delta$ of 3-colored faces. We use whisker plots (blue) to represent the entire ranges of computed values for a given parameter: boxes represent the middle 50% of values (25% - 75% percentile).

**LARGE REAL-WORLD GRAPHS.** To evaluate the balance quality of the Schnyder woods we plot the value $\delta_0$ and $\Delta$ as a function of $d_6$: our balanced Schnyder woods are compared to minimal ones in Fig. 6.10. Experimental results strongly suggests that our heuristic leads to well balanced Schnyder woods. Our heuristic performs particularly well for regular graphs, for which a large majority of vertices are balanced (79% in average for the sphere graph). The results are good also for irregular graphs (egea), where about 45% of vertices are balanced. In our experiments we observed that the choice of the initial seed has a limited effect on the balance of the resulting Schnyder wood. Minimal Schnyder woods represent a bad case, especially for regular graphs: most vertices have a large defect and the resulting paths $\Pi_0(v)$, $\Pi_1(v)$ and $\Pi_2(v)$ resemble very long spirals.

## 6.3 APPLICATION I: SCHNYDER DRAWINGS

While recent works [LSW16] provide a probabilistic study of the convergence for uniformly sampled triangulations endowed with a Schnyder wood, as far as we know there are no theoretical or empirical evaluations of the layout quality for regular graphs.

In this section our goal is to evaluate the impact of the balance of a Schnyder wood on the layout quality of the corresponding Schnyder drawings.
<figure><img src="image_120.png" /><figcaption>Figure 6.10: Balance of Schnyder woods for large graphs. For a given fixed choice of the initial seed we evaluate the proportion $\delta_0$ of balanced vertices (top charts) and the proportion $\Delta$ of 3-colored faces (bottom charts): we compare our heuristic (red) to the balance of minimal Schnyder woods (black). Dashed charts represent the results obtained after running the post-processing phase. The results are expressed as functions of $d_6$ (most regular graphs appear rightmost).</figcaption></figure>

**MOTIVATION.** A first qualitative evaluation of the graph layouts based on the balance Schnyder woods is provided by the pictures in Figures 6.11 and 6.13, showing the layouts corresponding to distinct Schnyder woods of the same graph, which confirm the following intuition. In the case of regular graphs, when starting from our well balanced Schnyder woods the shape of triangles is much more balanced, and the resulting drawing partially captures the regularity of the grid. When starting from an unbalanced Schnyder wood the drawing exhibits many long edges and flat triangles, a typical drawback of Schnyder drawings.

**MEASURING THE LAYOUT QUALITY.** As a quantitative measure of the quality of a graph layout we consider two parameters: the edge length and the aspect ratio of the faces. More precisely, as already done in Section 5.7 we compute the *edge lengths aesthetic metric* $\epsilon_l = 1 - d_{el}$, where $d_{el}$ is the average percent deviation of edge lengths defined by Equation 5.2 (obviously, in this chapter we consider the euclidean edge lengths). Observe that values of $\epsilon_l$ close to 1 mean that most edges have the same length, which is a desirable aesthetic criterion especially for regular graphs. We also use the *aspect ratio aesthetic metric*, denoted by $\alpha$, which can be defined in a similar way.

<figure><img src="image_121.png" /><figcaption>Figure 6.13: Schnyder drawings of the globe_5 graph.</figcaption></figure>
<figure><img src="image_122.png" /><figcaption>Figure 6.11: (left) A sphere graph endowed with our balanced Schnyder wood and the corresponding Schnyder drawing. The right pictures show the same portion of the Schnyder drawing: our balanced Schnyder wood leads to a much more readable and regular layout compared to the unbalanced case (right).</figcaption></figure>

<figure><img src="image_123.png" /><figcaption>Figure 6.12: Layout quality of Schnyder drawings for medium and large graphs (smallest graphs are listed leftmost). For a fixed choice of the root face we compute a balanced Schnyder wood with our heuristic and the minimal one: we compare the layout quality of the corresponding Schnyder drawings.</figcaption></figure>

**EXPERIMENTAL EVALUATION** The intuition, suggested by the layouts of Fig. 6.11 and Fig. 6.13, that balanced Schnyder woods lead to more pleasant and regular drawings, is also confirmed by the experiments involving several real-world and synthetic graphs. As shown by the charts in Fig. 6.12, the layouts corresponding to a balanced Schnyder woods always achieve better aesthetic criteria when compared with unbalanced Schnyder woods (in our tests we make use of the minimal one, which is strongly unbalanced).

To get a more quantitative evaluation, we consider some tiny graphs for which we are able to generate all possible Schnyder woods and compute the corresponding Schnyder drawings (with a fixed root face). Comparing the layout parameters we can state some interesting remarks: a more balanced Schnyder wood does not always necessarily guarantees to get a more pleasant Schnyder drawing, but this occurs very frequently. This is confirmed by our experiments shown in the charts of Fig. 6.14, reporting the values of several parameters (el, ar, as, well as the average edge length and aspect ratio) as a function of the average defect (as a measure of the balance). More precisely, we compute all distinct Schnyder woods of a rooted triangulation and we partition them according to the parameter $\delta_{avg}$ as a measure of their balance. For every class of Schnyder woods achieving more or less the
<figure><img src="image_124.png" /><figcaption>Figure 6.14: Comparison of layout quality: for each tiny graph we compute the edge length and aspect ratio metrics of the Schnyder drawings corresponding to our balanced Schnyder woods (compared to the drawing of a minimal Schnyder wood).</figcaption></figure>

<figure><img src="image_125.png" /><figcaption>Figure 6.15: Layout statistics of Schnyder drawings. We generate all distinct Schnyder woods of the globe_5 graph and we compute some statistics of the corresponding Schnyder drawings, according to the following aesthetic metrics: the average edge length (resp. aspect ratio) and the average percent deviation of edge Lent (resp. aspect ratio). We plot these statistics as a function of the average defect $\delta_{avg}$: balanced Schnyder woods have smaller values of $\delta_{avg}$ and are listed leftmost: for the globe_5 graph the values of $\delta_{avg}$ range in [1.25, 2.5].</figcaption></figure>

same balance, we make use of bar charts in order to plot the proportion of Schnyder drawings achieving a given value of the selected layout parameter. As shown by the plots in Fig. 6.15 for the case of the globe_5 graph, the layout quality tends to deteriorate as soon as Schnyder woods get more unbalanced: Schnyder woods with high values of $\delta_{avg}$ are more likely to get worst layout statistics.

## 6.4 APPLICATION II: SMALL SEPARATORS

### SMALL (CYCLE) SEPARATORS.
Now we consider the problem of computing small separators, which has been extensively investigated during the last four decades, due to its relevance for many graph algorithms [LT79; LT80; Mil86; ST96]. Given a graph G we consider small separators which are defined by a partition $(A, B, S)$ of all vertices such that S is a separating vertex set of small size (usually $|S| = O(\sqrt{|\bar{m}|})$), and the remaining vertices in $G \setminus S$ belong to a balanced partition $(A, B)$ satisfying $|A| \le \alpha n$, $|B| \le \alpha n$ (usually, for planar graphs, the balance ratio is $\alpha = 2/3$). Here we focus on simple cycle separators [Mil86], for which fast implementations [Hol+09; Fox+16]

Despite the large number of existing algorithmic solutions involving graph separators, we have not been able to find any working (and publicly available) implementation of planar separator theorems.
<figure><img src="image_126.png" /><figcaption>Figure 6.17: (top) A separator $(A, B, S)$ obtained from a Schnyder wood. (bottom) Example of cycles separators computed via balanced Schnyder woods: the quality of the solution strongly depends on the choice of the initial seed (the root face).</figcaption></figure>

have been recently proposed (some of them [Fox+16] are provided with a worst-case bound of $\sqrt{8m}$ on the cycle size).

### FROM SCHNYDER WOODS TO SIMPLE CYCLE SEPARATORS.
Schnyder woods provides a very fast procedure for partitioning, given an arbitrary inner vertex $v$, the set of inner faces of a triangulation into three sets $R_0(v)$, $R_1(v)$ and $R_2(v)$ (respectively blue, red and gray triangles in Fig. 6.3(b)), whose boundaries consist of the three disjoint paths $\Pi_0(v)$, $\Pi_1(v)$ and $\Pi_2(v)$ emanating from $v$. The computation of simple cycle separators can be done as follows: for each vertex $v$ check whether the two sets $A = \text{Int}(R_i(v) \cup R_{i+1}(v))$ and $B = \text{Int}(R_{i+2}(v))$ satisfy the prescribed balance ratio for at least one index $i \in \{0, 1, 2\}$ (indices are modulo 3, and $\text{Int}(R)$ denotes the set of inner vertices of a region $R$: then select the vertex for which the corresponding cycle length $|\Pi_i(v)| + |\Pi_{i+1}(v)| + 1$ is minimal (observe that, in practice, most vertices could lead to unbalanced partitions whose boundary size can be very large). All these steps can be performed almost instantaneously, since all the quantities above are encoded in the Schnyder drawing itself (see [Sch90] for more details). As far as we know there are no theoretical guarantees on both the partition balance and boundary size: in general, given an arbitrary Schnyder wood of a given triangulation, the procedure above does not lead to a short cycle separator (as depicted in Fig. 6.16). Nevertheless, our experiments seem to suggest that a balanced Schnyder wood is able to obtain good separators of short size for many classes of graphs; moreover, our approach is simple to implement and much faster than other existing solutions [Hol+09; Fox+16].

### EXPERIMENTAL EVALUATION.
In our experiments we look for separators with a balance ratio $\alpha = \frac{2}{3}$ that are short: the boundary size is at most $|S| \le \sqrt{8m}$, as required in [Fox+16]. We plot in the charts of Fig. 6.18 the boundary sizes and partition balances of the separators obtained from a

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

<figure><img src="image_128.png" /><figcaption>Figure 6.16: The separators corresponding to a balanced and an unbalanced Schnyder woods of a regular sphere graph.</figcaption></figure>

As observed in practice [Cas19], our Java implementation allows processing between 1.43M and 1.92M vertices per second. This has to be compared to the C implementations of previous results on cycle separators [Hol+09; Fox+16], running on an Intel Xeon X5650 2.67GHz (with 48.4 GB of RAM): the fastest variant of the procedures tested in [Fox+16] allows processing between 0.54M and 0.62M vertices per second for the case of square grids.
<figure><img src="image_129.png" /><figcaption>Figure 6.18: We evaluate the quality of the cycle separators obtained from our balanced Schnyder woods (tests are repeated with 200 random seeds). The top charts report the boundary sizes, while the bottom charts show the plots of the separator balance (the normalized size of the smallest of the two sets A and B). Graphs are listed from left to right according to the increasing values of their relative diameter.</figcaption></figure>

Schnyder drawing as described in Section 6.2. Our tests, repeated over several tens of graphs, confirm our intuition that balanced Schnyder woods lead to good separators for a large majority of classes of graphs.

As one could expect, the separator size and balance strongly depend on the balance of the underlying Schnyder wood, and their are also affected by the choice of the seed for graphs with large diameter: a good choice of the seed would prevent from getting too long cycles. For graphs with small diameter (e.g. random triangulations) Schnyder woods lead to very short separators, while the size is closed to $\sqrt{m}$ for most real-world graphs. In order to be fair we have to mention that our separators are often longer when compared with the results obtained in [Fox+16], but well below the prescribed bound of $\sqrt{8m}$.

### IMPROVING THE SEPARATOR QUALITY VIA POST-PROCESSING.
We already mentioned that it would be possible to perform a post-processing optimization in order to increase the balance of the Schnyder wood. As observed in our experiments the separator quality of the resulting Schnyder woods does not considerably improve after this post-processing phase: the plots in Fig. 6.19 show that the boundary size decreases less than 7% in most cases (on the tested meshes).

<figure><img src="image_130.png" /><figcaption>Figure 6.19: Separator quality: effect of post-processing optimization. For a fixed choice of the root face we compare the size of the separators obtained with our method, before and after performing the post-processing optimization.</figcaption></figure>
As shown throughout this manuscript Schnyder woods offer a very elegant and deep tool for dealing with graphs which are planar or embedded on surfaces, leading to extremely fast and memory efficient algorithmic solutions for solving several classes of graph problems. My impression is that Schnyder woods and related combinatorial structures have still many wonderful surprises in store for us. I list below a few open problems and lines of research that I find promising <fnref n="1" />.

## 7.1 GRAPHS ON SURFACES: OPEN QUESTIONS

### 7.1.1 Schnyder woods for graphs on surfaces

As already mentioned in Sections 3.4.2 and 6.1, there are many interesting open questions in the higher genus case involving both the combinatorial structure and the algorithmics of Schnyder woods.

For the case of simple toroidal triangulations a crucial question [Lév16] is the existence of 3-orientations that satisfy the definition of toroidal Schnyder woods while preserving the global spanning condition (the graphs induced by the edges of the three colors define three connected subgraphs). To our knowledge this question is still open.

No doubt, one very challenging question involves the existence and computation of orientations satisfying the multiple Schnyder local rule for simple triangulations of genus $g \ge 2$: according to our experimental results (Section 6.1) we conjecture the existence of such orientations even for graphs having small edge-width.

Finally, it would be interesting to further explore the algorithmics underlying the vertex shelling procedure. Can one devise a new shelling procedure for computing toroidal Schnyder woods satisfying the crossing condition? Is it possible to generalize the shelling procedure in order to compute 3-orientations and Schnyder woods in the genus $g \ge 2$ case? A positive answer could have a huge impact in practice from the algorithmic point of view, since the current results [Lév16; Sua21] for toroidal and higher genus graphs are not provided with practical implementations.

### 7.1.2 Drawing higher genus graphs (for $g > 1$)

As mentioned in Chapter 5, both the region-counting principle underlying Schnyder drawings and the *shift* method of the FPP algorithm have been extended to the toroidal case leading to periodic crossing-free grid drawings.

<footnote n="1">¹ Here I do not include my works involving graph encoding and visualizations problems for other classes of graphs, for which the kind of techniques described in this manuscript is not suitable. This occurs for instance in the case of graphs (such as complex networks) which do not exhibit a structure coming from a planar (or locally planar) embedding, and also in the case of graphs whose combinatorial structure can evolve over time (since the structure of Schnyder woods can dramatically change under local updates). In both cases these graphs require other kinds of mathematical tools and algorithmic techniques to deal with, and this goes beyond the scope of this manuscript.</footnote>
It remains open to devise efficient combinatorial algorithms for computing periodic drawings of graphs embedded on surfaces of genus $g \ge 2$. This problem is much more challenging, since it is not known how to combine the recent results on higher genus orientations [AGK16; Sua21] with the algorithmic techniques mentioned above.

### 7.1.3 Adaptive analysis: graph drawing and graph encoding

The recent experimental results presented in Chapter 6 would suggest that the study of regularity of Schnyder woods could be a new interesting research direction.

No doubt, the dependence of the layout quality of Schnyder drawings on the balance of the corresponding Schnyder woods has been little investigated to date. One very interesting and challenging problem would be to provide a theoretical analysis of the behaviour observed in Section 6.3, which seems to suggest that a much more pleasing layout could be obtained with a balanced Schnyder wood.

A promising line of research comes from the graph encoding perspective: motivated by some recent preliminary results<fnref n="2" />, we aim at designing new compression schemes and compact data structures which could be able to take profit of the regularity of triangle meshes. Our hope is to achieve better compression rates, while still guaranteeing rigorous upper bounds on the encoding size in the worst case. A crucial question concerns the choice of the size parameters (vertex degree distribution, proportion of degree 6 vertices, number of separating triangles, number of 3-colored faces, ...) to choose for establishing new adaptive bounds.

## 7.2 SCHNYDER WOODS FOR HIGHER DIMENSIONAL COMPLEXES

The study of Schnyder woods and related combinatorial structures in the case of higher dimensional complexes has been very little investigated so far [Eva+14; GI20]: this problem is fascinating and extremely challenging, mainly because the combinatorial structure of such objects is much richer and difficult to explore, compared to the case of planar (or local planar) graphs. One line of research could be to consider some nice classes of higher dimensional complexes (e.g. shellable, collapsible or vertex decomposable) which could be good candidates for generalizing some of the properties of Schnyder woods.

<footnote n="2">² In an ongoing and unpublished work (collaboration with Olivier Devillers) we have been able to improve the upper bound of 4n references per vertex stated in Theorem 4.8, when the input triangulation is regular (large majority of degree 6 vertices).</footnote>
[AL15] Noam Aigerman and Yaron Lipman. "Orbifold Tutte embeddings." In: *ACM Trans. Graph.* 34.6 (2015), 190:1–190:12.

[AGK16] Boris Albar, Daniel Gonçalves, and Kolja Knauer. "Orienting Triangulations." In: *J. Graph Theory* 83.4 (2016), pp. 392–405. URL: https://doi.org/10.1002/jgt.22005.

[AH78] M. O. Albertson and J. P. Hutchinson. "On the independence ratio of a graph." In: *J. Graph. Theory* 2 (1978), pp. 1–8.

[Ale00] Marc Alexa. "Merging polyhedral shapes with scattered features." In: *The Visual Computer* 16.1 (2000), pp. 26–37.

[AG05] Pierre Alliez and Craig Gotsman. "Recent Advances in Compression of 3D Meshes." In: *Advances in Multiresolution for Geometric Modelling*. Springer, 2005, pp. 3–26. URL: http://dx.doi.org/10.1007/3-540-26808-1_1.

[AJ05] Tyler J Alumbaugh and Xiangmin Jiao. "Compact array-based mesh data structures." In: *Proceedings of the 14th International Meshing Roundtable*. Springer, 2005, pp. 485–503. DOI: 10.1007/3-540-29090-7_29.

[BT06] János Barát and Carsten Thomassen. "Claw-decompositions and tutte-orientations." In: *J. Graph Theory* 52.2 (2006), pp. 135–146. URL: https://doi.org/10.1002/jgt.20149.

[Bar+12] Jérémy Barbay, Luca Castelli Aleardi, Meng He, and J Ian Munro. "Succinct representation of labeled graphs." In: *Algorithmica* 62.1-2 (2012), pp. 224–257. DOI: 10.1007/s00453-010-9452-7. URL: https://hal.inria.fr/hal-00712915v1.

[BHJ09] Mathieu Bastian, Sebastien Heymann, and Mathieu Jacomy. "Gephi: An Open Source Software for Exploring and Manipulating Networks." In: *Proc. of the Third Int. Conf. on Weblogs and Social Media*, ICWSM 2009, 2009. URL: https://doi.org/10.1007/PL00009264.

[BTV99] Giuseppe Di Battista, Roberto Tamassia, and Luca Vismara. "Output-Sensitive Reporting of Disjoint Paths." In: *Algorithmica* 23.4 (1999), pp. 302–340. URL: https://doi.org/10.1007/PL00009264.

[Bau72] Bruce G Baumgart. *Winged edge polyhedron representation*. Tech. rep. DTIC Document, 1972. URL: http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=AD0755141.

[Bau75] Bruce G Baumgart. "A polyhedron representation for computer vision." In: *Proceedings National Computer Conference and Exposition*. ACM. 1975, pp. 589–596. DOI: 10.1145/1499949.1500071.

[Bero7] O. Bernardi. "Bijective counting of tree-rooted maps and shuf-fle of parenthesis systems." In: *The Electronic Journal of Combinatorics* 14 (2007).

[BB07] O. Bernardi and N. Bonichon. "Catalans intervals and realizers of triangulations." In: *Proc. FPSAC07*. 2007.
[BB09] Olivier Bernardi and Nicolas Bonichon. "Catalan's intervals and realizers of triangulations." In: *Journal of Combinatorial Theory, Series A* 116.1 (2009). 22 pages, pp. 55-75. URL: https://hal.archives-ouvertes.fr/hal-00143870.

[BH18] Maciej Besta and Torsten Hoefler. "Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations." In: *CoRR* abs/1806.01799 (2018). arXiv: 1806.01799. URL: http://arxiv.org/abs/1806.01799.

[Boi+02] Jean-Daniel Boissonnat, Olivier Devillers, Sylvain Pion, Monique Teillaud, and Mariette Yvinec. "Triangulations in CGAL." In: *Computational Geometry: Theory & Applications* 22 (2002), pp. 5-19. DOI: 10.1016/S0925-7721(01)00054-2. URL: https://hal.inria.fr/inria-00167199.

[BGH03] N. Bonichon, C. Gavoille, and N. Hanusse. "An information-theoretic upper bound of planar graphs using triangulation." In: *STACS*. Springer, 2003, pp. 499-510.

[BGL05] N. Bonichon, C. Gavoille, and A. Labourel. "Edge partition of toroidal graphs into forests in linear time." In: *ICGT*. Vol. 22. 2005, pp. 421-425.

[Bon+06] N. Bonichon, C. Gavoille, N. Hanusse, D. Poulalhon, and G. Schaeffer. "Planar graphs, via well-orderly maps and trees." In: *Graphs and Combinatorics* 22.2 (2006), pp. 185-202.

[Bon02] Nicolas Bonichon. "Aspects algorithmiques et combinatoires des rØaliseurs des graphes plans maximaux." PhD thesis. Bordeaux I, 2002.

[Bon+10a] Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and David Ilcinkas. "Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces." In: *Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010*. 2010, pp. 266-278. URL: https://doi.org/10.1007/978-3-642-16926-7_25.

[Bon+10b] 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*. 2010, pp. 19-30. URL: https://doi.org/10.1007/978-3-642-14165-2_3.

[BW00] U. Brandes and D. Wagner. "A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs." In: *Algorithmica* 28.1 (2000), pp. 16-36. URL: https://doi.org/10.1007/s004530010029.

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

[Bro64] W. Brown. "Enumeration of triangulations of the disk." In: *Proc. London Math. Soc.* 3.14 (1964), pp. 515-528.

[CM07] Sergio Cabello and Bojan Mohar. "Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs." In: *Discrete & Comp. Geometry* 37.2 (2007), pp. 213-235.
[CKS98] Swen Campagna, Leif Kobbelt, and Hans-Peter Seidel. "Directed Edges—A Scalable Representation for Triangle Meshes." In: *Journal of Graphics Tools* 3 (1998), pp. 1–11. DOI: 10.1080/10867651.1998.10487494.

[Cas19] Luca Castelli Aleardi. "Balanced Schnyder Woods for Planar Triangulations: An Experimental Study with Applications to Graph Drawing and Graph Separators." In: *Graph Drawing and Network Visualization - 27th International Symposium, GD*. Vol. 11904. Lecture Notes in Computer Science. Springer, 2019, pp. 114–121. URL: https://doi.org/10.1007/978-3-030-35802-0\_9.

[CDF18a] Luca Castelli Aleardi, Gaspard Denis, and Éric Fusy. "Fast Spherical Drawing of Triangulations: An Experimental Study of Graph Drawing Tools." In: *17th International Symposium on Experimental Algorithms, SEA*. Vol. 103. LIPIcs. 2018, 24:1–24:14. URL: https://hal.archives-ouvertes.fr/hal-01761754.

[CD18] Luca Castelli Aleardi and Olivier Devillers. "Array-based compact data structures for triangulations: Practical solutions with theoretical guarantees." In: *J. Comput. Geom.* 9.1 (2018), pp. 247–289. URL: https://doi.org/10.20382/jocg.v9i1a8.

[CDF12] Luca Castelli Aleardi, Olivier Devillers, and Éric Fusy. "Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-Line Drawings." In: *Graph Drawing - 20th International Symposium*. 2012, pp. 376–387.

[CDF18b] 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 cylinder and torus." In: *J. Comput. Geom.* 9.1 (2018), pp. 391–429. URL: https://doi.org/10.20382/jocg.v9i1a14.

[CDM11] Luca Castelli Aleardi, Olivier Devillers, and Abdelkrim Mebarki. "Catalog Based Representation of 2D triangulations." In: *International Journal of Computational Geometry & Applications* 21 (2011), pp. 393–402. DOI: 10.1142/S021819591100372X. URL: http://hal.inria.fr/inria-00560400.

[CADR12] Luca Castelli Aleardi, Olivier Devillers, and Jarek Rossignac. "ESQ: Editable SQuad Representation for Triangle Meshes." In: *25th Conference on Graphics, Patterns and Images, SIBGRAPI* 2012. 2012, pp. 110–117. URL: http://dx.doi.org/10.1109/SIBGRAPI.2012.24.

[CDS05a] Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. "Dynamic updates of succinct triangulations." In: *Proceedings of the 17th Canadian Conference on Computational Geometry*. 2005, pp. 134–137. URL: http://www.cccg.ca/proceedings/2005/45.pdf.

[CDS05b] Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. "Succinct Representation of Triangulations with a Boundary." In: *Algorithms and Data Structures, 9th International Workshop, WADS*. Vol. 3608. Lecture Notes in Computer Science. Springer, 2005, pp. 134–145. URL: https://doi.org/10.1007/11534273\_13.
[CDS08] Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. "Succinct representations of planar maps." In: *Theor. Comput. Sci.* 408.2-3 (2008), pp. 174-187. URL: https://doi.org/10.1016/j.tcs.2008.08.016.

[CFK14] Luca Castelli Aleardi, Éric Fusy, and Anatolii Kostrygin. "Periodic Planar Straight-Frame Drawings with Polynomial Resolution." In: *LATIN 2014: Theoretical Informatics - 11th Latin American Symposium*. 2014, pp. 168-179.

[CAFL09] Luca Castelli Aleardi, Éric Fusy, and Thomas Lewiner. "Schnyder woods for higher genus triangulated surfaces, with applications to encoding." In: *Discrete & Computational Geometry* 42.3 (2009), pp. 489-516. URL: https://doi.org/10.1007/s00454-009-9169-z. URL: https://hal.inria.fr/hal-00712046v1.

[CFL10] Luca Castelli Aleardi, Éric Fusy, and Thomas Lewiner. "Optimal encoding of triangular and quadrangular meshes with fixed topology." In: *Proceedings of the 22nd Annual Canadian Conference on Computational Geometry*. 2010, pp. 95-98. URL: http://cccg.ca/proceedings/2010/paper27.pdf.

[Cha+12] Erin W. Chambers, David Eppstein, Michael T. Goodrich, and Maarten Löffler. "Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area." In: *J. Graph Algorithms Appl.* 16.2 (2012), pp. 243-259.

[CP95] M. Chrobak and T. H. Payne. "A Linear-Time Algorithm for Drawing a Planar Graph on a Grid." In: *Inf. Process. Lett.* 54.4 (1995), pp. 241-246.

[Chu+98] Richie Chih-Nan Chuang, Ashim Garg, Xin He, Ming-Yang Kao, and Hsueh-I Lu. "Compact encodings of planar graphs via canonical orderings and multiple parentheses." In: *Automata, Languages and Programming*. Springer, 1998, pp. 118-129. URL: https://doi.org/10.1007/BFb0055046.

[DFM01] Hubert De Fraysseix and Patrice Ossona de Mendez. "On topological aspects of orientations." In: *Discrete Mathematics* 229.1 (2001), pp. 57-72. URL: https://doi.org/10.1016/S0012-365X(00)00201-6.

[DGL17] Vincent Despré, Daniel Gonçalves, and Benjamin Lévêque. "Encoding Toroidal Triangulations." In: *Discrete & Computational Geometry* 57.3 (2017), pp. 507-544. URL: https://doi.org/10.1007/s00454-016-9832-0.

[Dha10] Raghavan Dhandapani. "Greedy Drawings of Triangulations." In: *Discrete & Computational Geometry* 43.2 (2010), pp. 375-392. URL: https://doi.org/10.1007/s00454-009-9235-6.

[DGK11] Christian A. Duncan, Michael T. Goodrich, and Stephen G. Kobourov. "Planar Drawings of Higher-Genus Graphs." In: *J. Graph Algorithms Appl.* 15.1 (2011), pp. 7-32.

[Ell+01] John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Gordon Woodhull. "Graphviz - Open Source Graph Drawing Tools." In: *Proc. of Graph Drawing*. 2001, pp. 483-484.

[Eva+14] William Evans, Stefan Felsner, Stephen G. Kobourov, and Torsten Ueckerdt. "Graphs admitting d-realizers: spanning-tree-decompositions and box-representations." In: *Proc. of EuroCG*. 2014.
[Fel04] S. Felsner. "Lattice structures from planar graphs." In: *Electronic Journal of Combinatorics* 11.15 (2004), p. 24.

[Fel01] Stefan Felsner. "Convex drawings of planar graphs and the order dimension of 3-polytopes." In: *Order* 18.1 (2001), pp. 19-37.

[Fel03] Stefan Felsner. "Geodesic Embeddings and Planar Graphs." In: *Order* 20.2 (2003), pp. 135-150. URL: https://doi.org/10.1023/B:ORDE.00000009251.68514.8b.

[FK12] J. Joseph Fowler and Stephen G. Kobourov. "Planar Preprocessing for Spring Embedders." In: *Graph Drawing - 20th International Symposium*. 2012, pp. 388-399.

[Fox+16] Eli Fox-Epstein, Shay Mozes, Phitchaya Mangpo Phothilimthana, and Christian Sommer. "Short and Simple Cycle Separators in Planar Graphs." In: *ACM Journal of Experimental Algorithmics* 21.1 (2016), 2.2:1-2.2:24.

[FPP90] Hubert de Fraysseix, János Pach, and Richard Pollack. "How to draw a planar graph on a grid." In: *Combinatorica* 10.1 (1990), pp. 41-51.

[FR91] Thomas M. J. Fruchterman and Edward M. Reingold. "Graph Drawing by Force-directed Placement." In: *Softw., Pract. Exper.* 21.11 (1991), pp. 1129-1164.

[FPS05] E. Fusy, D. Poulalhon, and G. Schaeffer. "Dissections and trees, with applications to optimal mesh encoding and to random sampling." In: *SODA*. 2005, pp. 690-699.

[Fus07] Eric Fusy. "Combinatoire des cartes planaires et applications algorithmiques." PhD thesis. Ecole Polytechnique, 2007.

[Ga093] Z. Gao. "A pattern for the asymptotic number of rooted maps on surfaces." In: *Journal of Combinatorial Theory, Series A* 64 (1993), pp. 246-264.

[GI20] Daniel Gonçalves and Lucas Isenmann. "Dushnik-Miller dimension of TD-Delaunay complexes." In: *Eur. J. Comb.* 88 (2020), p. 103110. URL: https://doi.org/10.1016/j.ejc.2020.103110.

[GL14] Daniel Gonçalves and Benjamin Lévêque. "Toroidal Maps: Schnyder Woods, Orthogonal Surfaces and Straight-Line Representations." In: *Discrete & Computational Geometry* 51.1 (2014), pp. 67-131. URL: http://dx.doi.org/10.1007/s00454-013-9552-7.

[GGT06] Steven J. Gortler, Craig Gotsman, and Dylan Thurston. "Discrete one-forms on meshes and applications to 3D mesh parameterization." In: *Comput. Aided Geom. Des.* 23.2 (2006), pp. 83-112. URL: https://doi.org/10.1016/j.cagd.2005.05.002.

[Goto3] Craig Gotsman. "On the Optimality of Valence-based Connectivity Coding." In: *Comput. Graph. Forum* 22.1 (2003), pp. 99-102. URL: https://doi.org/10.1111/1467-8659.t01-1-00649.

[GGS03] Craig Gotsman, Xianfeng Gu, and Alla Sheffer. "Fundamentals of spherical parameterization for 3D meshes." In: *ACM Trans. Graph.* 22.3 (2003), pp. 358-363.

[GS85] Leonidas Guibas and Jorge Stolfi. "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams." In: *ACM transactions on graphics (TOG)* 4.2 (1985), pp. 74-123. DOI: 10.1145/282918.282923.
[GR09] Topraj Gurung and Jarek Rossignac. "SOT: compact representation for tetrahedral meshes." In: *2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling*. ACM. 2009, pp. 79-88. DOI: 10.1145/1629255.1629266.

[Gur+11a] Topraj Gurung, Mark Luffel, Peter Lindstrom, and Jarek Rossignac. "LR: compact connectivity representation for triangle meshes." In: *ACM transactions on graphics (TOG)* 30.4 (2011). DOI: 10.1145/2010324.1964962.

[Gur+11b] Topraj Gurung, Daniel Laney, Peter Lindstrom, and Jarek Rossignac. "SQuad: Compact representation for triangle meshes." In: *Computer Graphics Forum* 30.2 (2011), pp. 355-364. DOI: 10.1111/j.1467-8659.2011.01866.x.

[Gur+13] Topraj Gurung, Mark Luffel, Peter Lindstrom, and Jarek Rossignac. "Zipper: A compact connectivity data structure for triangle meshes." In: *Computer-Aided Design* 45.2 (2013), pp. 262-269. URL: http://dx.doi.org/10.1016/j.cad.2012.10.009.

[HKL99] Xin He, Ming-Yang Kao, and Hsueh-I Lu. "Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings." In: *SIAM J. Discrete Math.* 12.3 (1999), pp. 317-325. URL: http://dx.doi.org/10.1137/S0895480197325031.

[Hol+09] Martin Holzer, Frank Schulz, Dorothea Wagner, Grigorios Prasinos, and Christos D. Zaroliagis. "Engineering planar separator algorithms." In: *ACM Journal of Experimental Algorithmics* 14 (2009). URL: https://doi.org/10.1145/1498698.1571635.

[IS05] M. Isenburg and J. Snoeyink. *Graph Coding and Connectivity Compression*. 2005. URL: http://www.cs.unc.edu/~isenburg/papers/is-gccc-04.pdf.

[KTO1] Marcelo Kallmann and Daniel Thalmann. "Star-vertices: a compact representation for planar meshes with adjacency information." In: *Journal of Graphics Tools* 6.1 (2001), pp. 7-18. DOI: 10.1080/10867651.2001.10487533.

[Kan96] Goos Kant. "Drawing Planar Graphs Using the Canonical Ordering." In: *Algorithmica* 16.1 (1996), pp. 4-32. URL: https://doi.org/10.1007/BF02086606.

[Ket99] Lutz Kettner. "Using generic programming for designing a data structure for polyhedral surfaces." In: *Comput. Geom.* 13.1 (1999), pp. 65-90. URL: https://doi.org/10.1016/S0925-7721(99)00007-3.

[KR99] Davis King and Jarek Rossignac. "Guaranteed 3.67v bit encoding of planar triangle graphs." In: *Proc. of the 11th Canadian Conf. on Comp. Geom.* 1999. URL: http://www.cccg.ca/proceedings/1999/c39.pdf.

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

[Kob13] Stephen G. Kobourov. "Force-Directed Drawing Algorithms." In: *Handbook on Graph Drawing and Visualization*. 2013, pp. 383-408.
[KW05] Stephen G. Kobourov and Kevin Wampler. "Non-Euclidean Spring Embedders." In: *IEEE Trans. Vis. Comput. Graph.* 11.6 (2005), pp. 757-767.

[Kuto6] Martin Kutz. "Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time." In: *SoCG*. 2006, pp. 430-438.

[Laz+01] Francis Lazarus, Michel Pocchiola, Gert Vegter, and Anne Verroust. "Computing a canonical polygonal schema of an orientable triangulated surface." In: *SoCG*. 2001, pp. 80-89.

[Lév16] Benjamin Lévêque. *Generalization of Schnyder woods to orientable surfaces and applications*. 2016. URL: https://tel.archives-ouvertes.fr/tel-01488943.

[LLT03] Thomas Lewiner, Hélio Lopes, and Geovan Tavares. "Optimal discrete Morse functions for 2-manifolds." In: *Comput. Geom.* 26.3 (2003), pp. 221-233. URL: https://doi.org/10.1016/S0925-7721(03)00014-2.

[LSW16] Yiting Li, Xin Sun, and Samuel S. Watson. *Schnyder woods, SLE(16), and Liouville quantum gravity*. Tech. rep. arXiv:1705.03573v1 [math.PR]. ArXiv, 2016. URL: https://arxiv.org/abs/1705.03573.

[LT79] Richard J. Lipton and Robert E Tarjan. "A Separator Theorem for Planar Graphs." In: *SIAM J. Applied Math.* 36.2 (1979), pp. 177-189.

[LT80] Richard J. Lipton and Robert Endre Tarjan. "Applications of a Planar Separator Theorem." In: *SIAM J. Comput.* 9.3 (1980), pp. 615-627. URL: https://doi.org/10.1137/0209046.

[Lis99] Valery A. Liskovets. "A Pattern of Asymptotic Vertex Valency Distributions in Planar Maps." In: *J. Comb. Theory, Ser. B* 75.1 (1999), pp. 116-133. URL: https://doi.org/10.1006/jctb.1998.1870.

[Lop+03] Hélio Lopes, Jarek Rossignac, Alla Safonova, Andrzej Szymczak, and Geovan Tavares. "Edgebreaker: a simple implementation for surfaces with handles." In: *Computers & Graphics* 27.4 (2003), pp. 553-567.

[Mag+15] Adrien Maglo, Guillaume Lavoué, Florent Dupont, and Céline Hudelot. "3D Mesh Compression: Survey, Comparisons, and Emerging Trends." In: *ACM Comput. Surv.* 47.3 (2015), 7:1-7:41. URL: http://dx.doi.org/10.1145/2693443.

[McDo8] Colin McDiarmid. "Random graphs on surfaces." In: *J. Comb. Theory, Ser. B* 98.4 (2008), pp. 778-797. URL: https://doi.org/10.1016/j.jctb.2007.11.006.

[Meng4] Patrice Ossona de Mendez. "Orientations bipolaires." PhD thesis. Paris, 1994.

[Mil86] Gary L. Miller. "Finding Small Simple Cycle Separators for 2-Connected Planar Graphs." In: *J. Comput. Syst. Sci.* 32.3 (1986), pp. 265-279. URL: https://doi.org/10.1016/0022-0000(86)90030-9.

[Moh96] Bojan Mohar. "Straight-line representations of maps on the torus and other flat surfaces." In: *Discret. Math.* 155.1-3 (1996), pp. 173-181. URL: https://doi.org/10.1016/0012-365X(94)00381-R.
[MR98] Bojan Mohar and Pierre Rosenstiehl. "Tessellation and Visibility Representations of Maps on the Torus." In: *Discret. Comput. Geom.* 19.2 (1998), pp. 249–263. URL: https://doi.org/10.1007/PL00009344.

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

[NSI04] Hiroshi Nagamochi, Takahisa Suzuki, and Toshimasa Ishii. "A simple recognition of maximal planar graphs." In: *Inf. Process. Lett.* 89.5 (2004), pp. 223–226.

[NR04] Takao Nishizeki and Md. Saidur Rahman. *Planar Graph Drawing*. Vol. 12. Lecture Notes Series on Computing. World Scientific, 2004. URL: https://doi.org/10.1142/5648.

[PS06] Dominique Poulalhon and Gilles Schaeffer. "Optimal coding and sampling of triangulations." In: *Algorithmica* 46.3-4 (2006), pp. 505–527. DOI: 10.1007/s00453-006-0114-8.

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

[Ros99] Jarek Rossignac. "Edgebreaker: Connectivity compression for triangle meshes." In: *Visualization and Computer Graphics, IEEE Transactions on* 5.1 (1999), pp. 47–61. DOI: 10.1109/2945.764870.

[Sab+05] S. Saba, I. Yavneh, C. Gotsman, and A. Sheffer. "Practical Spherical Embedding of Manifold Triangle Meshes." In: *SMI2005*. 2005, pp. 258–267.

[Sch89] Walter Schnyder. "Planar graphs and poset dimension." In: *Order* (1989), pp. 323–343.

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

[SS99] Jack Snoeyink and Bettina Speckmann. "Tripod: a minimalist data structure for embedded triangulations." In: *Workshop on Comput. Graph Theory and Combinatorics*. 1999. URL: https://www.win.tue.nl/~speckman/papers/Tripod.pdf.

[ST96] Daniel A. Spielman and Shang-Hua Teng. "Disk Packings and Planar Separators." In: *Proc. of the Twelfth Annual Symposium on Computational Geometry*, 1996. 1996, pp. 349–358.

[Sua21] Jason Suagee. "Existence and Construction of Schnyder Orientations over a Large Class of Higher Genus Surface Triangulations." PhD thesis. George Washington University, 2021.

[Sul17] Thom Sulanke. "Generating Maps on Surfaces." In: *Discret. Comput. Geom.* 57.2 (2017), pp. 335–356. URL: https://doi.org/10.1007/s00454-016-9853-8.

[SL09] Thom Sulanke and Frank H. Lutz. "Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds." In: *Eur. J. Comb.* 30.8 (2009), pp. 1965–1979. URL: https://doi.org/10.1016/j.ejc.2008.12.016.
[Tar74] R.E. Tarjan. "A note on finding the bridges of a graph." In: *Inf. Process. Lett.* 2 (1974), pp. 160-161.

[Tur84] G. Turan. "On the succinct representation of graphs." In: *Discrete & Applied Mathematics* 8 (1984), pp. 289-294.

[Tut62] W. Tutte. "A census of planar triangulations." In: *Canadian Journal of Mathematics* 14 (1962), pp. 21-38.

[Tut63] W. Tutte. "How to draw a graph." In: *Proc. of London Math. Soc.* 13 (1963), pp. 734-767.

[VY90] Gert Vegter and Chee-Keng Yap. "Computational Complexity of Combinatorial Surfaces." In: *SoCG*. 1990, pp. 102-111.

[WKS01] D. Neilson W. Kocay and R. Szypowski. "Drawing graphs on the torus." In: *Ars Combinatoria* 59 (2001), pp. 259-277.

[Walo3] Chris Walshaw. "A Multilevel Algorithm for Force-Directed Graph-Drawing." In: *J. Graph Algorithms Appl.* 7.3 (2003), pp. 253-285.

[ZRS06] Rhaleb Zayer, Christian Rössl, and Hans-Peter Seidel. "Curvilinear Spherical Parameterization." In: *Int. Conf. on Shape Modeling and Applications (SMI 2006)*. 2006, p. 11.

[ZJ16] Qingnan Zhou and Alec Jacobson. "Thingi10K: A Dataset of 10,000 3D-Printing Models." In: *CoRR abs/1605.04797* (2016). URL: http://arxiv.org/abs/1605.04797.

[Zit94] Arjana Zitnik. "Drawing Graphs on Surfaces." In: *SIAM J. Discret. Math.* 7.4 (1994), pp. 593-597. URL: https://doi.org/10.1137/S0895480192242006.
<figure><img src="image_131.png" /></figure>
3-orientation, 10, 36

4-scheme triangulation, 62

α-orientation
definition, 10

α-orientation
accessible, 36
minimal, 36

x-span, 53

annular representation, 6

barycentric embedding, 49

bridge, 20

brins, 5

canonical ordering
computation, 11
definition, 11

canonical tree, 36

chord, 6

chord diagram, 12

chordal edge, 6

combinatorial map
definition, 5

compression rate, 32

conquer operator, 20

conquest, 12

contractible edge, 13, 75

corner, 5

cut-graph, 7, 52

darts, 5

drawing
periodic, 51
straight-frame, 52
straight-line, 51

dual forest, 24, 53

edge-width, 7

Edgebreaker, 32

embedding
cellular, 5

face-width, 7, 61

facial-walk, 5

flat
cylinder, 6
torus, 7

force-directed, 49

free vertex

definition, 12

half-edge data structure, 14

half-edges, 5

information-theory bound, 32

map
cylindric, 6
dual, 7
essentially 3-connected, 7
essentially simple, 7

merge
operator, 19

planar graph, 6
polygonal scheme
canonical, 7

quasi-triangulation, 6

river, 70

Schnyder
paths, 11
regions, 11

Schnyder wood
computation, 11
definition, 10
minimal, 36
toroidal, 26

Schnyder woods
crossing, 27, 52
separating edge, 20
separating triangle, 13
shelling, 11
spanning sub-graph, 7
split
operator, 19

tambourine, 59
definition, 8

triangulation
cylindric, 6
irreducible, 75
plane, 6
simple, 6
toroidal, 6

triangulations
fixed topology, 35

weakly convex, 61