# Algorithms for graphs on surfaces: from graph drawing to graph encoding

Luca Castelli Aleardi

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

## To cite this version:

Luca Castelli Aleardi. Algorithms for graphs on surfaces: from graph drawing to graph encoding. Computational Geometry [cs.CG]. Université Paris Cité, 2022. tel-04354325

HAL Id: tel-04354325

https://theses.hal.science/tel-04354325

Submitted on 19 Dec 2023

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

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

Public Domain
MÉMOIRE D'HABILITATION À DIRIGER DES RECHERCHES

(spécialité Informatique)

Université Paris Cité

ALGORITHMS FOR GRAPHS ON SURFACES: FROM GRAPH
DRAWING TO GRAPH ENCODING

LUCA CASTELLI ALEARDI

Soutenue publiquement le 27 juin 2022 en visio-conférence devant le jury composé de:

<table><tr><td>Nicolas BONICHON</td><td>MdC, HDR</td><td>Université de Bordeaux</td><td></td></tr><tr><td>Erin WOLF CHAMBERS</td><td>Professeur</td><td>Saint Louis University</td><td>(rapporteur)</td></tr><tr><td>Giuseppe DI BATTISTA</td><td>Professeur</td><td>Università Roma Tre</td><td>(rapporteur)</td></tr><tr><td>Stefan FELSNER</td><td>Professeur</td><td>Technische Universität Berlin</td><td>(rapporteur)</td></tr><tr><td>Claire MATHIEU</td><td>DR CNRS</td><td>Université Paris Cité</td><td></td></tr></table>
COMPLETE PUBLICATION LIST

Most results presented in this manuscript are not new and correspond to
works published after my PhD. The results obtained during my PhD are
not included in this manuscript.

PUBLICATIONS OBTAINED AFTER MY PHD

Journals

[J6] L. Castelli Aleardi, É. Fusy and O. Devillers. Canonical ordering for graphs on the cylinder, with applications to periodic straight-line drawings on the flat cylinder and torus. *J. of Computational Geometry (JoCG)*, 9(1): 391-429, 2018. Chap. 3, 5

[J5] L. Castelli Aleardi and O. Devillers. Array-based compact data structures for triangulations: Practical solutions with theoretical guarantees. *Journal of Computational Geometry (JoCG)*, 9(1): 247-289, 2018. Chap. 4

[J4] J. Barbay, L. Castelli Aleardi, M. He and J. I. Munro, Succinct Representation of Labeled Graphs. *Algorithmica* 62(1-2): 224-257 (2012). /

[J3] L. Castelli Aleardi, É. Fusy and T. Lewiner. Schnyder woods for higher genus triangulated surfaces, with applications to encoding. *Discrete and Computational Geometry (special issue of SoCG 2008)*, 32(3): 489-516, 2009. Chap. 3, 4

Book chapters

[B1] L. Castelli Aleardi, O. Devillers, and J. Rossignac. Triangulation Data Structures. In *Encyclopedia of Algorithms* 2016, Springer, p.2262-2267, 2016. Chap. 4
International conferences

[C15] L. Castelli Aleardi. Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators. In Proc. of 27th Int. Symposium on Graph Drawing and Network Visualization (GD 2019), Springer LNCS, vol. 11904, p. 114-121, 2019. Chap. 6

[C14] L. Castelli Aleardi, S. Salihoglu, G. Singh and M. Ovsjanikov. Spectral Measures of Distortion for Change Detection in Dynamic Graphs. In Proc. of 7th Int. Conference on Complex Networks and Their Applications (Complex Networks 2018), Springer SCI, vol. 813, p. 54-66, 2018. /

[C13] L. Castelli Aleardi, G. Denis and É. Fusy. Fast spherical drawing of planar triangulations: an experimental study of graph drawing tools. In Proc. of 17th Int. Symposium on Experimental Algorithms (SEA 2018), LIPIcs, 24:1-24:14, 2018. Chap. 5

[C12] L. Castelli Aleardi, A. Nolin and M. Ovsjanikov. Efficient and practical tree preconditioning for solving Laplacian systems. In Proc. of 14th Int. Symp. on Experimental Algorithms (SEA 2015), LNCS, vol. 9125, p. 219-231, 2015. /

[C11] L. Castelli Aleardi, É. Fusy and A. Kostrygin. Periodic planar straight-frame drawings with polynomial resolution. In Proc. of 11th Latin American Theoretical Informatics Symposium (LATIN 2014), LNCS, vol. 8392, p. 168-179, 2014. Chap. 5

[C10] L. Castelli Aleardi, O. Devillers, and É. Fusy. Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings. In Proc. 20th Int Symp. on Graph Drawing (GD 2012), LNCS, vol. 7704, p. 376-387, 2012. Chap. 5

[C9] L. Castelli Aleardi, O. Devillers, and J. Rossignac. ESQ: Editable SQuad representation for triangle meshes. In Proc. of XXV SIBGRAPI - Conf. on Graphics, Patterns and Images (Sibgrapi 2012), IEEE Comp. Soc., p. 110-117, 2012. /

[C8] L. Castelli Aleardi and O. Devillers. Explicit array-based compact data structures for triangulations. In Proc. of the 22nd Int. Symp. on Algorithms and Computation (ISAAC 2011), LNCS, vol. 7074, p. 312-323. Chap. 4

[C7] L. Castelli Aleardi, É. Fusy and T. Lewiner. Optimal encoding of triangular and quadrangular meshes with fixed topology, in Proc. of the 22nd Canadian Conf. on Comp. Geom. (CCCG 2010), p. 95-98, 2010. Chap. 4

[C6] L. Castelli Aleardi, É. Fusy and T. Lewiner. Schnyder woods for higher genus triangulated surfaces, in Proc. of the 24th annual ACM Symp. on Computational Geometry (SoCG 2008), p. 311-319. Chap. 3, 4

[C5] J. Barbay, L. Castelli Aleardi, M. He and I. J. Munro. Succinct representations of labeled graphs, in Proc. of the 18th Int. Sym. on Algorithms and Computation (ISAAC 2007), LNCS, vol. 4835, p. 316-328. /

PUBLICATIONS OBTAINED DURING MY PHD

Journals

[J2] L. Castelli Aleardi, O. Devillers and Abdelkrim Mebarki. Catalog based representation of 2D triangulations. Internat. J. Comput. Geom. Appl., 21(4): 393-402, 2011. /

[J1] L. Castelli Aleardi, O. Devillers and Gilles Schaeffer. Succinct representations of planar maps, Theoretical Computer Science (special issue in honor of F. Preparata), 408:174-187, 2008. /

International conferences

[C4] L. Castelli Aleardi, O. Devillers and G. Schaeffer. Optimal succinct representations of planar maps, in Proc. of the 22nd annual ACM Symposium on Computational Geometry (SoCG 2006), p. 309-318. /

[C3] L. Castelli Aleardi, O. Devillers et A. Mebarki. 2D Triangulation representation using stable catalogs, in Proc. of the 18th Canadian Conference on Computational Geometry (CCCG 2006), p. 71-74. /

[C2] L. Castelli Aleardi, O. Devillers et G. Schaeffer. Succinct representation of triangulations with a boundary, in Proc. of the 9th Workshop on Algorithms and Data Structures (WADS 2005), LNCS, vol. 3608, p. 134-145. /

[C1] L. Castelli Aleardi, O. Devillers and G. Schaeffer. Dynamic updates of succinct triangulations, in Proc. of the 17th Canadian Conference on Computational Geometry (CCCG 2005), p. 135-138. /
I extend my gratitude to my parents, Manlio Castelli and Maria Grazia Aleardi, and my family for their unwavering love and support. Their consistent encouragement bolstered me through the challenging and fulfilling phases of my academic journey.

I would like to acknowledge that the works presented in this collection are the result of collaborative efforts, symbolizing collective achievements. I appreciate all my co-authors and numerous colleagues for the enriching and enjoyable moments shared during our research endeavors and beyond.

Special thanks are due to the reviewers and the entire jury for their valuable constructive feedback and for generously committing their time to this process. I am sincerely grateful for their involvement in this academic endeavor.
<figure><img src="image_2.png" /></figure>
CONTENTS

1 INTRODUCTION 1

1.1 Motivation 1

1.2 My contributions 1

1.2.1 Schnyder woods and canonical orderings in higher genus (Chapter 3) 2

1.2.2 Graph encoding and practical compact data structures (Chapter 4) 2

1.2.3 Drawing graphs on surfaces (Chapter 5) 3

1.2.4 Fast implementations and experimental results (Chapter 6) 4

1.3 Overview of the manuscript 4

2 PRELIMINARIES 5

2.1 Graphs and maps (on surfaces) 5

2.1.1 Definitions 5

2.1.2 Planarizing graphs on surfaces 8

2.2 Schnyder woods (and canonical orderings) 10

2.2.1 Schnyder woods and canonical orderings for plane triangulations: definition 10

2.2.2 Computing Schnyder woods (and canonical orderings) in the plane 11

2.3 Implementations and experimental settings 14

3 SCHNYDER WOODS AND CANONICAL ORDERINGS FOR NON PLAIN GRAPHS 17

3.1 Dealing with higher genus graphs 17

3.2 g-Schnyder woods for triangulations of arbitrary genus 18

3.2.1 The definition 18

3.2.2 Existence of g-Schnyder woods 19

3.2.3 Spanning properties of g-Schnyder woods 23

3.3 Canonical ordering for cylindrical simple triangulations 24

3.4 Schnyder woods for toroidal triangulations 26

3.4.1 The definition of Gonçalves and Lévêque [GL14] (for the triangulated case) 26

3.4.2 Existence of toroidal Schnyder woods 28

3.4.3 Our contribution: toroidal Schnyder woods via vertex shellings 29

4 GRAPH ENCODING AND COMPACT DATA STRUCTURES 31

4.1 Related works 31

4.1.1 Tree-based encodings 31

4.1.2 Optimal encodings achieving information-theory lower bounds 32

4.2 Encoding triangulations in arbitrary genus 32

4.2.1 Encoding in higher genus 33

4.3 Our contribution: optimal encoding of triangulations with fixed topology 35

4.3.1 Encoding plane triangulations (Poulalhon and Schaeffer [PS06] bijection) 36

4.3.2 Encoding planar triangulations with multiple boundaries 37

4.3.3 Encoding in higher genus 38
<table>
  <tbody>
    <tr>
      <td>4.4</td>
      <td>Compact mesh data structures: related works</td>
      <td>39</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>Our contribution: compact data structures for triangulations</td>
      <td>40</td>
    </tr>
    <tr>
      <td>4.5.1</td>
      <td>Our first solution: scheme description</td>
      <td>41</td>
    </tr>
    <tr>
      <td>4.5.2</td>
      <td>Further reducing the space requirements</td>
      <td>43</td>
    </tr>
    <tr>
      <td>4.5.3</td>
      <td>Additional features</td>
      <td>44</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>Experimental Results</td>
      <td>46</td>
    </tr>
    <tr>
      <td>4.6.1</td>
      <td>Preprocessing: construction vs. decoding.</td>
      <td>46</td>
    </tr>
    <tr>
      <td>4.6.2</td>
      <td>Mesh navigation: runtime performances</td>
      <td>46</td>
    </tr>
    <tr>
      <td>5</td>
      <td>DRAWING GRAPHS ON SURFACES</td>
      <td>49</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Graph Drawing in the plane ("as I have known it")</td>
      <td>49</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Drawings higher genus graphs: related works</td>
      <td>51</td>
    </tr>
    <tr>
      <td>5.2.1</td>
      <td>Grid-drawings of toroidal graphs: combinatorial algorithms</td>
      <td>52</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Our contribution: periodic toroidal drawings</td>
      <td>53</td>
    </tr>
    <tr>
      <td>5.3.1</td>
      <td>Drawing cylindrical simple triangulations (with no chord at Γ<sub>inn</sub>).</td>
      <td>53</td>
    </tr>
    <tr>
      <td>5.3.2</td>
      <td>Drawing cylindrical triangulations having chords at Γ<sub>inn</sub>.</td>
      <td>57</td>
    </tr>
    <tr>
      <td>5.3.3</td>
      <td>Periodic drawings on the torus</td>
      <td>59</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Our contribution: periodic straight-frame drawings</td>
      <td>62</td>
    </tr>
    <tr>
      <td>5.4.1</td>
      <td>Related works: description of the algorithm of Duncan et al. [DGK11]</td>
      <td>62</td>
    </tr>
    <tr>
      <td>5.4.2</td>
      <td>Our modified version of the algorithm: aligning vertical coordinates</td>
      <td>63</td>
    </tr>
    <tr>
      <td>5.4.3</td>
      <td>A new binary decomposition for 4-scheme triangulations</td>
      <td>65</td>
    </tr>
    <tr>
      <td>5.4.4</td>
      <td>Final remarks</td>
      <td>66</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Spherical Drawings of planar graphs</td>
      <td>67</td>
    </tr>
    <tr>
      <td>5.5.1</td>
      <td>Related works</td>
      <td>67</td>
    </tr>
    <tr>
      <td>5.6</td>
      <td>Our contribution: a fast spherical drawing with theoretical guarantees</td>
      <td>69</td>
    </tr>
    <tr>
      <td>5.7</td>
      <td>Experimental results</td>
      <td>70</td>
    </tr>
    <tr>
      <td>5.7.1</td>
      <td>Spherical drawings</td>
      <td>70</td>
    </tr>
    <tr>
      <td>5.7.2</td>
      <td>Spherical preprocessing for Euclidean spring embedders</td>
      <td>72</td>
    </tr>
    <tr>
      <td>6</td>
      <td>SOME EXPERIMENTAL RESULTS ON SCHNYDER WOODS</td>
      <td>75</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Experimental results on higher genus Schnyder woods</td>
      <td>75</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Balance of planar Schnyder woods</td>
      <td>76</td>
    </tr>
    <tr>
      <td>6.2.1</td>
      <td>Our heuristic for well balanced Schnyder woods</td>
      <td>77</td>
    </tr>
    <tr>
      <td>6.2.2</td>
      <td>Experimental evaluation</td>
      <td>79</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>Application I: Schnyder drawings</td>
      <td>79</td>
    </tr>
    <tr>
      <td>6.4</td>
      <td>Application II: Small separators</td>
      <td>82</td>
    </tr>
    <tr>
      <td>7</td>
      <td>CONCLUDING REMARKS AND PERSPECTIVES</td>
      <td>85</td>
    </tr>
    <tr>
      <td>7.1</td>
      <td>Graphs on surfaces: open questions</td>
      <td>85</td>
    </tr>
    <tr>
      <td>7.1.1</td>
      <td>Schnyder woods for graphs on surfaces</td>
      <td>85</td>
    </tr>
    <tr>
      <td>7.1.2</td>
      <td>Drawing higher genus graphs (for g > 1)</td>
      <td>85</td>
    </tr>
    <tr>
      <td>7.1.3</td>
      <td>Adaptive analysis: graph drawing and graph encoding</td>
      <td>86</td>
    </tr>
    <tr>
      <td>7.2</td>
      <td>Schnyder woods for higher dimensional complexes</td>
      <td>86</td>
    </tr>
    <tr>
      <td>BIBLIOGRAPHY</td>
      <td></td>
      <td>87</td>
    </tr>
    <tr>
      <td>INDEX</td>
      <td></td>
      <td>96</td>
    </tr>
  </tbody>
</table>
## 1.1 MOTIVATION

Graphs and networks play a relevant role in modern science: graphs are clearly fundamental in computer science and related fields (e.g. discrete mathematics) and they provide powerful tools for abstraction in many other research domains, as they allow us to represent a collection of entities together with their interactions, as done in social networks and biological processes.

This manuscript focuses on the algorithmics of graphs which come with an extra topological and combinatorial structure, given by an embedding in the plane or on a surface of bounded genus (they are also referred to as *maps*). These graphs are among the most important objects in several application domains, as they correspond to the combinatorial structure underlying 3D meshes (one of the the most used representations for describing a discrete approximation of a surface). The wide diffusion and the increasing complexity of planar and surface meshes motivated a large number of works, in the last two decades, addressing the problems of efficiently processing, representing and visualizing such objects. Consequently, my research is at the frontier between several domains, ranging from computational geometry and geometry processing to combinatorics, graph drawing and data structures.

**COMBINATORIAL STRUCTURES FOR PLANAR GRAPHS.** Planar graphs exhibit many important structural properties: one of the nicest characterizations is the one provided by *Schnyder woods*, a deep combinatorial structure which is able to finely capture the notion of planarity of a graph. Schnyder woods have been introduced by W. Schnyder to define a new planarity criterion in terms of poset dimensions [Sch89], as well as a very elegant and simple straight-line drawing algorithm [Sch90]. The most classical formulation is for the family of plane triangulations, yielding the following striking property: the internal edges of a triangulation can be partitioned into three trees that span all inner vertices and are rooted respectively at each of the three vertices incident to the outer face (as illustrated in Fig. 1.1). This nice global characterization in terms of spanning trees motivated a large number of generalizations and applications in several domains such as graph drawing, graph encoding, random sampling, succinct representations and plane spanners [Sch90; Chu+98; HKL99; BTV99; Fel01; BGH03; PS06; FPS05; Bon+06; Bar+12; CDS08; Bon+10b; Bon+10a; Dha10].

<figure><img src="image_3.png" /><figcaption>Figure 1.1: A plane triangulation endowed with a Schnyder wood.</figcaption></figure>

## 1.2 MY CONTRIBUTIONS

Previous existing works on Schnyder woods and related structures (e.g. canonical orderings) focused mainly on their applications to graph drawing and encoding, and on their extensions [Kan96; BTV99; Fel01] to other classes of planar graphs (e.g. 3-connected plane graphs).

In this manuscript we focus on triangulations and, more precisely, we will consider triangulations embedded on surfaces of arbitrary genus.
<figure><img src="image_4.png" /><figcaption>Figure 1.2: Example of g-Schnyder wood in the toroidal case.</figcaption></figure>

### 1.2.1 Schnyder woods and canonical orderings in higher genus (Chapter 3)

As often occurs when dealing with combinatorial objects, the most difficult question involving a generalization is to find the proper definitions of such objects, and to prove their existence. In a work in collaboration with E. Fusy and T. Lewiner [CAFL09] we proposed the first generalization of Schnyder woods for the case of triangulations of higher arbitrary genus. One main contribution of this work is to show how to extend the computation of a canonical ordering (based on an incremental shelling algorithm) to the case of triangulations of genus g. As a by-product, we define a g-Schnyder wood which generalizes the planar well known structure preserving the global spanning properties: roughly speaking, in the higher genus case is possible to obtain an edge orientation where most of vertices still respect the local original Schnyder rule, while a small set of at most 4g vertices may have more than 3 outgoing incident edges (see Fig. 1.2 for an illustration).

Since then, the study of orientations for graphs on surfaces has attracted more attention [GL14; AGK16; DGL17; KGL19; Sua21]. In particular, different generalizations of Schnyder woods and canonical orderings have been proposed in the toroidal case for graph drawing purposes [GL14; CDF18b].

### 1.2.2 Graph encoding and practical compact data structures (Chapter 4)

A general way to encode the combinatorial information of a graph embedded on a surface consists in choosing a (vertex) spanning tree T and to encode the tree T along with the set edges not lying in the tree. This approach, combined with Schnyder woods and canonical orderings, leads in the planar case to efficient linear-time encoding schemes. For instance, for the class of plane triangulations having n vertices, the Schnyder tree decomposition allow us to encode a triangulation [HKL99] with at most 4n bits using multiple parenthesis words: this encoding is very elegant and simple to implement, achieving a compression rate which is quite close to the information theory optimal bound of 3.24n bits.

**ENCODING HIGHER GENUS TRIANGULATIONS.** The graph encoding problem was one of the main motivations for introducing our generalization of Schnyder woods [CAFL09]. A consequence of our definition of g-Schnyder woods is that the global spanning condition can be preserved: the spanning tree decomposition of Schnyder woods (of the planar case) translates into the existence of a partition of the edges into a cut-graph (a map embedded on a surface having one face) more two spanning maps of genus g. This tool allowed us to obtain a new encoding of genus g triangulations of size at most $4n + (g \log n)$ bits, which matches the bound of the Edgebreaker compression scheme [Ros99], being quite closed to the theoretical minimum bound of $3.24n + \Omega(g \log n)$ bits.

**SPACE-EFFICIENT DATA STRUCTURES.** We also consider the graph encoding problem in a different setting: in a work in collaboration with O. Devillers [CD18] we address the problem of designing practical compact data structures, allowing us to efficiently perform local navigation and answer adhacency queries, while requiring a small amount of memory resources. More precisely, we show how to exploit the spanning tree decomposition provided

<footnote n="1">¹ As we have shown in [CFL10], this bound is achieved combining efficient planarizing strategies with our optimal encoding of planar triangulations with multiple boundaries (see Section 4.3).</footnote>
by Schnyder woods in order to design new parsimonious data structures for planar triangulations: when using (maximal) Schnyder woods, it is possible to represent a triangulation of size n with at most 4n references, supporting navigation in worst case O(1) time.

Moreover, a nice feature of our data structure is that it can be decoded in a streamable way (without memory overhead) directly from the compressed format for triangulations mentioned above (combining Schnyder woods and parenthesis words): this overcomes a common limitation of previous compact data structures, which require an intermediate (non-compact) mesh representation for running the pre-processing construction phase.

I have implemented this solution and performed tests on large triangle meshes having tens of millions of vertices, and its practical interest is confirmed by our experiments: it is possible to reduce considerably the amount of memory consumption (common mesh representations requires between 13n and 19n references) while supporting fast navigation in practice.

### 1.2.3 Drawing graphs on surfaces (Chapter 5)

The problem of computing crossing-free drawings of planar graphs has attracted a lot of attention from both the combinatorial and algorithmic point of views in the last four decades. Several solutions exist allowing us to obtain pleasing layouts achieving several aesthetic criteria, that help the readability and the exploration of the graph structure. The Koebe's circle packing approach, Tutte's spring embedding [Tut63], the shift-based FPP method [FPP90] or the face-counting principle by Schnyder [Sch90] are among the most widely studied algorithmic paradigms for computing crossing-free layouts in the planar case (the pictures in Fig. 1.3 show the Tutte and Schnyder drawings of a random planar triangulation).

In this manuscript we focus on the problem of computing crossing-free layouts of graphs embedded on surfaces, which is very challenging and has been investigated less frequently.

### PERIODIC DRAWINGS OF TOROIDAL MAPS.
In a work [CDF12] in collaboration with E. Fusy and O. Devillers we observed that the shift-based FPP algorithm [FPP90] can be reformulated and adapted to deal with toroidal triangulations. In particular, it is be possible to extend the notion of canonical orderings to cylindrical triangulations: once a pair of parallel non-contractible cycles is chosen (a so-called tambourine), this leads to a new linear time (planar) drawing of a toroidal simple triangulation with n vertices, on a grid of size $O(n^2 \times n)$. The main advantage of our approach, compared to previous works [DGK11], is the possibility to obtain an xy-periodic drawings in the flat torus, which leads to a periodic tiling of the plane (see Fig. 1.4 for an illustration). This approach is also suitable to deal with the more general case of essentially 3-connected toroidal maps [CDF18b]. To our knowledge, our algorithms for computing periodic drawings in the flat torus achieve the best known bounds on the grid resolution for both the triangular and 3-connected case. For instance, the face-counting principle [GL14] leads to a periodic drawing on a grid of size $O(n^2) \times O(n^2)$ (in the case of simple triangulations, without loops or multiple edges), and layouts of $O(n^3)$ area can be obtained with a variation of the shift algorithm [DGK11] (but not satisfying the periodicity constraints).

In another work, with E. Fusy and A. Kostrygin [CFK14], we solved an interesting open question (mentioned in [Cha+12; DGK11]) which consists

<figure><img src="image_5.png" /><figcaption>Figure 1.3: Planar straight-line drawings of a random planar triangulation with 100 vertices. (top) Tutte's barycentric embedding. (bottom) Schnyder drawing.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 1.4: A periodic drawing of a toroidal triangulation in the flat torus (obtained with our modified version of the FPP algorithm).</figcaption></figure>
in obtaining a planar grid drawing achieving simultaneously three criteria: polynomial area, and a straight-frame which is xy-periodic and whose boundary corresponds to a polygonal scheme of the graph.

**SPHERICAL DRAWINGS.** The problem of drawing a planar graph with a prescribed boundary can also be applied to another important problem: the one of computing a geodesic spherical drawings of a genus 0 graph, which has many applications in geometric processing and computer graphics (also known as *spherical parameterization problem*). More precisely, we have devised an efficient and practical algorithm for computing a geodesic spherical drawing of a planar graph with polynomial resolution (Castelli Aleardi, Denis, and Fusy [CDF18a]). Quite interestingly, according to our experiments the computation of a spherical drawing can prove to be useful to provide good initial layouts for running 3D spring embedders (see Fig. 1.5): a good initial configuration does help to better and faster untangle the graph.

1.2.4 Fast implementations and experimental results (Chapter 6)

A significant part of some works [CD18; CDF18a; Cas19] has been devoted to the experimental evaluation of the performances of the combinatorial algorithms relying on Schnyder woods and canonical orderings. All experimental results and graph layouts presented in this manuscript have been obtained with my own Java implementations performing tests on several classes of graphs (having up to several millions of vertices): our experiments confirm the efficiency of combinatorial algorithms in terms of both running time and memory requirements. Beside the applications to graph drawing and graph encoding, it turns out the Schnyder woods have proven to be useful for other algorithmic problems involving planar graphs, such as the computation of cycle separators [Cas19].

1.3 OVERVIEW OF THE MANUSCRIPT

This document is intended to be self-contained as much as possible. The reader who is familiar with the main concepts of topological graph theory and combinatorics of planar maps may skip Chapter 2. Chapters 4 and 5 are independent and are conceived as short surveys providing the main recent advances concerning the problems of drawing and encoding graphs embedded on surfaces. For the sake of clarity and concision this document provides a high level and informal presentation of my works in the domains of graph drawing and graph encoding. I put strong emphasis on the advantages of Schnyder woods as deep tool for dealing with the algorithmics of graphs embedded on surfaces. My goal is to provide an intuition of the proofs underlying the main results, while skipping most technical details. Proofs are omitted or sometimes only sketched: the interested reader can refer to the published works for the complete proofs and missing details.

DISCLAIMER. The vast majority of results, both theoretical and experimental, are not new and appeared in journal or conference publications that I co-authored: this document reproduces large passages and some figures from these works. The only exception are the algorithmic proof for the computation of a toroidal Schnyder wood (described in Section 3.4.3), which can be seen as a by-product of our results on cylindrical maps, and the experimental results on Schnyder woods in genus $g \ge 1$ (Section 6.1).

<figure><img src="image_7.png" /><figcaption>Figure 1.5: (bottom) 3D layout of a random triangulation with 5k faces. This layout is obtained running the FR spring embedder [FR91] using as initial layout a spherical drawing of the triangulation (top).</figcaption></figure>
## 2.1 GRAPHS AND MAPS (ON SURFACES)

For the sake of completeness, we provide a very brief description of the necessary concepts of topological graph theory we will need in this manuscript. The interested reader can find a more comprehensive and detailed discussion of these notions in [MTo1].

### 2.1.1 Definitions

**GRAPH EMBEDDINGS AND TOPOLOGICAL MAPS.** A graph $M$ on a surface is a graph $G = (V, E)$ embedded without edge-crossings on a closed orientable surface $S$ (such a surface is specified by its genus $g$, i.e., the number of handles).

If the components of $S \setminus G$ are homeomorphic to topological disks, then $M$ is a so-called (topological) map (in this case the underlying graph $G$ is necessarily connected). A subgraph $G' = (V', E')$ of $G$ is called cellular if the components of $S \setminus G'$ are homeomorphic to topological disks, i.e., the graph $G'$ equipped with the embedding inherited from $G$ is a map.

Note that a map has more structure than a graph, since the edges around each vertex are in a certain cyclic order. In addition, a map has faces (the components of $M \setminus S$). By the Euler relation, the genus $g$ of the surface on which $M$ is embedded satisfies

$$2 - 2g = \chi(M) = |V| - |E| + |F|,$$

where $\chi(M)$ is the Euler characteristic of $M$, and $V, E$, and $F$ are the sets of vertices, edges, and faces in $M$.

From the algorithmic point of view it is convenient to view each edge $e = \{u, v\} \in E$ as made of two brins $^1$, originating respectively at $u$ and at $v$, the two brins meeting in the middle of $e$; the two brins of $e$ are said to be opposite to each other. The follower of a brin $h$ is the next brin after $h$ in clockwise order (shortly cw) around the origin $v$ of $h$. A facial walk is a cyclic sequence $(b_1, \dots, b_k)$, where for $i \in [1..k]$, $b_{i+1}$ (with the convention that $b_{k+1} = b_1$) is the opposite brin of the follower of $b_i$. A facial walk corresponds to a walk along the boundary of a face $f$ of $M$ in ccw order (i.e., with the interior of $f$ on the left).

The face incident to a brin $h$ is defined as the face on the left of $h$ when one looks toward the origin of $h$. Note that to a brin $h$ of $M$ corresponds a corner of $M$, which is the pair $c = (h, h')$ where $h'$ is the follower of $h$. The vertex incident to $c$ is defined as the common origin of $h$ and $h'$, and the face $f$ incident to $c$ is defined as the face of $M$ in the sector delimited by $h$ and $h'$ (so $f$ coincides with the face incident to $h$).

**COMBINATORIAL MAPS.** Maps can also be defined in a combinatorial way. A combinatorial map $M$ is a connected graph $G = (V, E)$ where one

A cellular embedding of a graph $G$ is a crossing-free drawing of $G$ on a surface $S$ or, more precisely, a one-to-one map from $G$ to $S$ such that every vertex of $G$ is map to a point on $S$ and every edge $(u, v)$ is represented as a simple path (curve) between the images of $u$ and $v$. Moreover, the drawing is required to be crossing-free: the images of two distinct edges cannot cross (they meet only at their endpoints), and the images of edges cannot pass through the points images of vertices.

<footnote n="1">¹ Sometimes brins are also called darts in the literature. Brins are essentially equivalent to half-edges, which are at the core of popular data structures for representing graph embeddings [Ket99]: we refer to Section 2.3 for a more detailed presentation.</footnote>
<figure><img src="image_8.png" /><figcaption>Figure 2.1: A cylindric triangulation with boundary faces $B_{\text{inn}} = \{\text{a, b, c, d}\}$ and $B_{\text{ext}} = \{\text{h, i, j, k}\}$. Left: annular representation. Right: x-periodic representation.</figcaption></figure>

specifies a cyclic order for the set of brins (half-edges) around each vertex. One defines facial walks of a combinatorial map as above (note that the above definition of a facial walk as a certain cyclic sequence of brins does not need an embedding, it just requires the cyclic cw order of the brins around each vertex). One obtains from the combinatorial map a topological map by attaching a topological disk at each facial walk; and the genus $g$ of the corresponding surface satisfies again $2 - 2g = |V| - |E| + |F|$, with $F$ the number of topological disks (facial walks), which are the faces of the obtained topological map [MT01].

**(PLANE) TRIANGULATIONS.** In this document we will focus mainly on triangulations: more precisely, a (*simple*) triangulation $\mathcal{T}$ is a map with no loops nor multiple edges and with all faces of degree 3 (each face has 3 edges on its contour). If $\mathcal{T}$ is a *plane triangulation* the edges and vertices of incident to the outer face are called the *outer edges* and *outer vertices*. The other ones are called the *inner edges* and *inner vertices*. Most of times we deal with triangulations (or maps) which are *rooted*, having a distinguished root face.

When the outer face is polygonal (degree greater than three) and all inner faces are triangular we have a so-called *quasi-triangulation*.

**CYLINDRIC AND TOROIDAL MAPS.** A cylindric map is a planar map with two marked faces $B_{\text{inn}}$ and $B_{\text{ext}}$ whose boundaries $\Gamma_{\text{inn}}$ and $\Gamma_{\text{ext}}$ are simple cycles ($\Gamma_{\text{inn}}$ and $\Gamma_{\text{ext}}$ might share vertices and edges). The faces $B_{\text{inn}}$ and $B_{\text{ext}}$ are respectively called the *inner boundary-face* and the *outer boundary-face*. The other faces are called *inner faces*. If all inner faces are triangle then we have a so-called *cylindric triangulation*. Boundary vertices and edges are those belonging to $\Gamma_{\text{inn}}$ (gray circles in Fig. 2.1) or $\Gamma_{\text{ext}}$ (black circles in Fig. 2.1); the other ones are called *inner vertices* (white circles in Fig. 2.1) and edges. We also define a *chordal edge*, or *chord*, at $\Gamma_{\text{inn}}$ as an edge not on $\Gamma_{\text{inn}}$ but with its two ends on $\Gamma_{\text{inn}}$. Similarly a *chord* at $\Gamma_{\text{ext}}$ is an edge not on $\Gamma_{\text{ext}}$ but with its two ends on $\Gamma_{\text{ext}}$.

A toroidal triangulation is a map on the torus with only triangular faces (the map is called *simple* if it has no loop nor multiple edges).

**PERIODIC REPRESENTATIONS OF CYLINDRIC AND TOROIDAL MAPS.** We will often consider cylindric maps in the annular representation where $B_{\text{ext}}$ is the outer face, as shown in Fig. 2.1(left). Sometimes we will draw cylindric (resp. toroidal) maps using the periodic representation in the flat cylinder (resp. torus).

For $w > 0$ and $h > 0$, the *flat cylinder* of width $w$ and height $h$ is the rectangle $[0, w] \times [0, h]$ where the vertical sides are identified (see right picture in Fig. 2.1). A point on this cylinder is located by two coordinates

A graph is planar if it admits an embedding on the sphere $S^2$ or, equivalently, if it can be embedded into the plane. A plane graph is a graph endowed with its planar embedding.

In our drawings of plane triangulations the root face will coincide with the infinite outer face.

Through this work special attention will be paid to graphs embedded on the cylinder and on the torus (motivated by visualization purposes, in Chapter 5).

<figure><img src="image_9.png" /><figcaption>Figure 2.2: A toroidal triangulation and its periodic representation in the flat torus.</figcaption></figure>
$x \in \mathbb{R}/w\mathbb{Z}$ and $y \in [0, h]$. The *flat torus* of width $w$ and height $h$ is the rectangle $[0, w] \times [0, h]$ where both pairs of opposite sides are identified. A point on this torus is located by two coordinates $x \in \mathbb{R}/w\mathbb{Z}$ and $y \in \mathbb{R}/h\mathbb{Z}$. Figure 2.2 shows the drawing of a simple toroidal triangulation in the flat torus.

**NON-CONTRACTIBLE CYCLES, CUT-GRAPHS, POLYGONAL SCHEMES.** A subgraph $G' = (V', E')$ is *spanning* if $V' = V$. A *cut-graph* of $M$ is a spanning cellular subgraph $G' = (V', E')$ with a unique face, i.e., $S \setminus G'$ is homeomorphic to a topological disk (the example of Fig. 2.3 shows a cut-graph of a toroidal triangulation). A non-contractible curve is a closed curve that cannot be continuously deformed to a point. Such a curve is called *proper* if it meets $G$ only at vertices (not at edges); the *length* of a proper non-contractible curve is the number of vertices it meets. A *non-contractible cycle* (also called *fundamental cycle*) of $G$ is a (simple) cycle of edges of $G$ that forms a non-contractible curve (the length of such a cycle is its number of edges).

In our setting, where we deal with a graph $G$ embedded on a surface $S$, we consider a *canonical polygonal scheme* as a collection of $2g$ fundamental cycles, with a common vertex $v$, such that cutting $S$ along these cycles lead to a topological disk.

**ESSENTIALLY SIMPLE TRIANGULATIONS AND 3-CONNECTED MAPS.** A cylindric map is called *simple* if it has no loops nor multiple edges, and is called *essentially simple* if it has no loops nor multiple edges in the periodic representation. Note that an essentially simple cylindric map might have 2-cycles and 1-cycles (loops), which have to be *non-contractible* (they have $B_{\text{inn}}$ on one side and $B_{\text{ext}}$ on the other side), and two loops cannot be incident to the same vertex.

A toroidal map is called *essentially simple* if its periodic representation in the plane is simple. A toroidal map is called *3-connected* if it is 3-connected as a graph, and is called *essentially 3-connected* if its periodic representation<fnref n="2" /> in the plane is 3-connected (see Fig. 2.4).

**EDGE-WIDTH AND FACE-WIDTH.** The *face-width* of $G$ is the minimum of the lengths of the proper non-contractible curves for $G$. The *edge-width* of a toroidal map $G$ is the minimum of the lengths of the non-contractible cycles of $G$. For a cylindric map, the *edge-distance* $d$ between the two boundaries is the length of a shortest possible path starting from a vertex of $\Gamma_{\text{inn}}$ and ending at a vertex of $\Gamma_{\text{ext}}$ (possibly $d=0$).

**DUALITY.** The *dual* of a (topological) map $M$ is the map $M^*$ on the same surface defined as follows: $M^*$ has a vertex in each face of $M$, and each edge $e$ of $M$ gives rise to a *dual edge* $e^*$ in $M^*$, which connects the vertices of $M^*$ corresponding to the faces of $M$ sharing $e$. Note that the adjacencies between the vertices of $M^*$ correspond to the adjacencies between the faces of $M$. Duality for edges can be refined into duality for brins: the dual of a brin $h$ of an edge $e$ is the brin of $e^*$ originating from the face incident to $h$ (the face on the left of $h$ when looking toward the origin of $h$). Note that the dual of the dual of a brin $h$ is the opposite brin of $h$.

<figure><img src="image_10.png" /><figcaption>Figure 2.3: A toroidal triangulation and a cut-graph spanning all its vertices.</figcaption></figure>

LCA: *controller fundamental cycle*.

<figure><img src="image_11.png" /><figcaption>Figure 2.4: An essentially 3-connected toroidal map.</figcaption></figure>

<footnote n="2">² The periodic representation (also called universal cover) is obtained by gluing an infinite number of translated copies of our drawing, assembling the right (resp. upper) side of one copy with the left (resp. lower) side of another. Then a non contractible loop become an edge linking two different translated copies of the same point.</footnote>
### 2.1.2 Planarizing graphs on surfaces

A possible solution to deal with algorithmic problems involving higher genus graphs consists in performing a planarization of the surface. Actually, given a triangulation $\mathcal{T}$ with $n$ vertices on a surface $S$ of genus $g$, one can compute a cut-graph or a collection of $2g$ non-trivial cycles, whose removal makes $S$ a topological disk (possibly with boundaries). For example some work makes it possible to compute polygonal schemas in time $O(gn)$ for a triangulated orientable manifold [Laz+01; VY90]. Nevertheless a planarization approach would not be always best suited in some cases: from the combinatorial point of view this would imply to deal with boundaries of arbitrary size (arising from the planarization procedure), as non-trivial cycles can be of size $\Omega(\sqrt{n})$, and cut-graphs have size $O(gn)$. Moreover, from the algorithmic complexity point of view, the most efficient procedures for computing small non-trivial cycles [CM07; Kuto6] require more than linear time, the best known bound being currently of $O(n \log n)$ time.

#### Planarizing toroidal graphs

When dealing with toroidal graphs the planarization problem becomes easier, especially when there are no loops and no multiple edges: depending on the intended purpose one can cut along one or more non-contractible cycles, leading for instance to cylindric maps or pairs of subgraphs which are planar.

**TAMBOURINE.** Let $M$ be a toroidal map, and let $\Gamma_1, \Gamma_2$ be a pair of homotopic non-contractible cycles of $M$ that are oriented in the same direction. The pair $\Gamma_1, \Gamma_2$ is called a *tambourine* if the area $A$ between $\Gamma_1$ and $\Gamma_2$ — on the right of $\Gamma_1$ and on the left of $\Gamma_2$— is a "ribbon of faces", i.e., $A$ is face-connected and the set of edges dual to edges in $A\{(\Gamma_1, \Gamma_2)\}$ forms a non-contractible cycle homotopic to $\Gamma_1$ and $\Gamma_2$. The drawing of Fig. 2.5 gives an example of such a configuration. Note that $\Gamma_1$ and $\Gamma_2$ might share vertices and edges. In its master's thesis Arnaud Labourel (see also [BGL05]) shows that any toroidal triangulation admits a tambourine decomposition, more precisely

**Proposition 2.1 ([BGL05])** Let $\mathcal{T}$ be a simple toroidal triangulation and let $\Gamma$ be a non-contractible cycle of $\mathcal{T}$. Then there is a tambourine $\Gamma_1, \Gamma_2$ of $\mathcal{T}$ whose two cycles are homotopic to $\Gamma$. Moreover one can compute such a tambourine in linear time.

It turns out that this statement holds more generally for essentially 3-connected toroidal maps, as we proved in [CDF18b].

**CUTTING A TOROIDAL TRIANGULATION ALONG THREE CYCLES.** Another way of planarizing a toroidal triangulation $\mathcal{T}$ consists in cutting along three non-contractible and non-homotopic cycles (whose intersection is a single vertex), which leads to a decomposition of $\mathcal{T}$ into two plane quasi-triangulations $^3$. See Fig. 2.6 for an example. The correctness of this approach relies on the following fact (cited in [GL14] as unpublished result):

<figure><img src="image_12.png" /><figcaption>Figure 2.5: Cutting along two parallel non-contractible cycles: the toroidal triangulation is decomposed into a tambourine (green faces) and a cylindric map (gray faces).</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 2.6: Three non-contractible and non-homotopic cycles crossing at vertex 1</figcaption></figure>

<footnote n="3">³ This planarization approach has been used to prove the existence of Schnyder wood for simple toroidal triangulations: the solution proposed by Gonçalves and Lévêque [GL14] will be sketched in Section 3.4</footnote>
**Proposition 2.2 (Fijavz)** Any simple toroidal triangulation $\mathcal{T}$ contains three non-contractible and non-homotopic cycles $\Gamma_1, \Gamma_2$ and $\Gamma_3$ whose intersection is a single vertex (they are pairwise disjoint otherwise).
<figure><img src="image_14.png" /><figcaption>Figure 2.7: A rooted plane triangulation with 10 vertices, with root face ($V_0, V_1, V_2$) (a), endowed with a Schnyder wood (b). Picture (c) shows the local Schnyder condition around inner vertices.</figcaption></figure>

An $\alpha$-orientation of a graph $G = (V, E)$ (where $\alpha: V \to N$) is a choice of a direction for each edge, such that for each vertex $v \in V$, there are exactly $\alpha(v)$ outgoing edges incident to $v$.

## 2.2 SCHNYDER WOODS (AND CANONICAL ORDERINGS)

There are several equivalent formulations of Schnyder woods, either in terms of *angle labeling* (Schnyder labeling) or *edge coloring and orientation* or in terms of orientations with prescribed out-degrees. In this manuscript we focus on the formulation given in terms of edge orientations for the family of plane triangulations.

Schnyder woods, and more generally $\alpha$-orientations, received a great deal of attention: from the combinatorial point of view, the set of Schnyder woods of a fixed triangulation has an interesting lattice structure [Bre00; Bon02; Fel04; DFM01; Men94], and the nice characterization in terms of spanning trees motivated a large number of applications in graph drawing, graph coding and random sampling [Sch90; Chu+98; HKL99; BTV99; Fel01; BGH03; Fus07; PS06; FPS05; Bon+06; Bar+12].

### 2.2.1 Schnyder woods and canonical orderings for plane triangulations: definition

In this manuscript the labels are also referred to as colors. The edges of color 0 will be drawn as red segments or curves, while we will use blue and black segments for edges of color 1 and 2 respectively.

We recall here the definition of Schnyder woods for plane triangulations given in terms of edge colorings and orientations (illustrated in Figure 2.7).

**Definition 2.3 (Schnyder [Sch90])** Let $\mathcal{T}$ be a plane triangulation, and denote by $V_0, V_1, V_2$ the outer vertices in counterclockwise (ccw) order around the outer face. A Schnyder wood of $\mathcal{T}$ is an orientation and labeling, with labels in $\{0, 1, 2\}$, of the inner edges of $\mathcal{T}$ so as to satisfy the following conditions:

* **root-face condition:** for $i \in \{0, 1, 2\}$, the inner edges incident to the outer vertex $v_i$ are all ingoing of color $i$.

* **local condition for inner vertices:** For each inner vertex $v$, the edges incident to $v$ in counterclockwise (ccw) order are: one outgoing edge colored 2, zero or more incoming edges colored 1, one outgoing edge colored 0, zero or more incoming edges colored 2, one outgoing edge colored 1, and zero or more incoming edges colored 0, which we write concisely as

$$(\text{Seq}(\text{In}1), \text{Out}0, \text{Seq}(\text{In}2), \text{Out}1, \text{Seq}(\text{In}0), \text{Out}2).$$

While the definition is given in terms of local conditions, the main structural property, as stated in Fact 2.4, is more global, namely a partition of the inner edges into 3 trees (please refer [Bre00] for more details).

**Fact 2.4 (Schnyder [Sch90])** Each plane triangulation $\mathcal{T}$ admits a Schnyder wood. Given a Schnyder wood on $\mathcal{T}$, the three directed graphs $T_0, T_1, T_2$ induced by the edges of color 0, 1, 2 are trees that span all inner vertices and are naturally rooted at $V_0, V_1$, and $V_2$, respectively.

A Schnyder wood of a plane triangulation $\mathcal{T}$ defines a so-called 3-orientation of $\mathcal{T}$: all inner vertices have exactly 3 outgoing edges (and outer vertices have no outgoing edges).
Another important consequence of the local Schnyder condition is that one gets a partition of the inner faces of a triangulation following the three paths in $T_0, T_1, T_2$ starting at an inner vertex v. More precisely we have:

**Fact 2.5 (Schnyder [Sch90])** Let us consider a plane triangulation $\mathcal{T}$ endowed with a Schnyder wood, and the three paths $\Pi_i(v)$ (for $i \in \{0,1,2\}$) in $T_i$ from an inner vertex v to the vertex $V_i$ on the root face. Then the paths $\Pi_0, \Pi_1$ and $\Pi_2$ are disjoint (the only share vertex v) and provide a partition of the $2n-5$ inner faces of $\mathcal{T}$ into three regions $R_0(v), R_1(v)$ and $R_2(v)$ (as illustrated in Fig. 2.8).

This simple fact is crucial for designing efficient grid drawing algorithms, as sketched in Chapter 5.

**CANONICAL ORDERINGS.** Another important combinatorial structure, closely related to Schnyder woods, is given in terms of a shelling order on the vertices of a graph. For the case of plane triangulations, *canonical orderings* can be defined in the following way (see Fig. 2.9):

**Definition 2.6 ([FPP90])** Let $\mathcal{T}$ be a plane triangulation, whose vertices on the outer (root) face are denoted $V_0, V_1, V_2$. An ordering $\pi = \{v_1, v_2, \dots, v_n\}$ of the $n$ vertices of $\mathcal{T}$ is called a *canonical ordering* if the subgraphs $G_k$ ($3 \le k \le n$) induced by the vertices $v_1, \dots, v_k$ satisfy the following conditions (where we denote by $B_k$ the cycle bounding the outer face of $G_k$):

* $G_k$ is 2-connected and internally triangulated, and $G_n = \mathcal{T}$;

* $v_1$ and $v_2$ belong to the outer face ($V_0, V_1, V_2$);

* for each $k \ge 3$ the vertex $v_k$ is on the $B_k$ and its neighbors in $G_{k-1}$ are consecutive on $B_{k-1}$.

It is worth noting that canonical orderings and their generalizations are a very versatile tool for dealing with the algorithmics of planar graphs, from graph drawing to graph encoding, as we will in the next chapters.

### 2.2.2 Computing Schnyder woods (and canonical orderings) in the plane

In view of the generalization of Schnyder woods to higher genus, for the sake of completeness we quickly review two procedures for computing Schnyder woods (we mainly focus on the case of plane triangulations): one approach is based on a *vertex shelling procedure*, while the second makes use of *edge contractions*. Both approaches have been generalized independently, leading to different definitions of Schnyder woods for higher genus surfaces [CAFL09; GL14]: Chapter 3 will be devoted to illustrate these results.

#### Vertex shelling

We first review a well-known linear time algorithm designed for computing a Schnyder wood of a plane triangulation, following the presentation by Brehm [Bre00]. It is convenient here to consider a plane triangulation as embedded on the sphere $S^2$, with a marked face that plays the role of the outer face. The procedure consists in growing a region C, called the *conquered region*, delimited by a simple cycle B (B is considered as part of C) $^4$. Initially C consists of the root-face (as well as its incident edges and vertices). A *chordal*

<figure><img src="image_15.png" /><figcaption>Figure 2.8: This picture illustrates the partition into three regions $R_i(v_6)$ defined by the three paths $\Pi_i(v_6)$ emanating from vertex $v_6$.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Figure 2.9: A sequence of graphs $\{G_k\}_{k \le n}$ corresponding to a canonical ordering of a triangulation $\mathcal{T}$ ($n = 10$).</figcaption></figure>

<footnote>$^4$ In the figures, the faces of $\mathcal{T} \setminus C$ are shaded.</footnote>
<figure><img src="image_17.png" /><figcaption>Figure 2.12: This figure illustrates the linear-time shelling procedure that computes a (maximal) Schnyder wood of a plane triangulation. The algorithm consists in performing $n-2$ vertex conquests, while maintaining a simple boundary cycle B (or-ange edges) enclosing the region that remains to be visited (gray faces). At the beginning (a) the boundary cycle coincides with the outer cycle ($V_0, V_1, V_2$). In order to ensure that B remains always simple (and the gray region simply connected), we avoid removing vertices on B that are incident to chordal edges (connecting two vertices on B). To get the maximal Schnyder wood it suffices to perform, at each step, the conquest of the free vertex closest to $V_1$.</figcaption></figure>

edge is defined as an edge not in C but with its two extremities on B. A free vertex is a vertex of $B \setminus \{V_0, V_1\}$ with no incident chordal edges. One defines the conquest of such a vertex $v$ as the operation of transferring to C all faces incident to $v$, as well as the edges and vertices incident to these faces; the boundary B of C is easily verified to remain a simple cycle. Associated with a conquest is a simple rule (depicted in Figure 2.10) to color and orient the edges incident to $v$ in the exterior region. Let $v_r$ be the right neighbor and $v_l$ the left neighbor of $v$ on B, looking toward $C \setminus \{v\}$ (in the figures, toward the shaded area). Orient outward of $v$ the two edges ($v, v_r$) and ($v, v_l$); assign color 0 to ($v, v_r$) and color 1 to ($v, v_l$). Orient toward $v$ and color 2 all edges exterior to C incident to $v$ (these edges are between ($v, v_r$) and ($v, v_l$) in ccw order around $v$).

<figure><img src="image_18.png" /><figcaption>Figure 2.10: Vertex conquest</figcaption></figure>

The algorithm for computing a Schnyder wood of a plane triangulation with $n$ vertices is a sequence of $n-2$ conquests of free vertices, together with the operations of coloring and orienting the incident edges (the initial conquest, always applied to the vertex $V_2$, is a bit special: the edges going to the right and left neighbors are not colored nor oriented, since these are outer edges).

<figure><img src="image_19.png" /><figcaption>Figure 2.11: In a planar chord diagram with a root-edge $e = \{V_0, V_1\}$, there must be a vertex $v$ not incident to $e$ nor to any chord.</figcaption></figure>

The correctness and termination of the traversal algorithm described above is based on the following fundamental property illustrated in Figure 2.11. A planar chord diagram (i.e., a topological disk with chordal edges that do not cross each other) with root-edge $\{V_0, V_1\}$ always has on its boundary a vertex $v \notin \{V_0, V_1\}$ not incident to any chord, see for instance [Breoo] for a detailed proof.

One proves that the structure computed by the traversal algorithm is a Schnyder wood by considering some invariants (see Figure 2.13):

* the edges that are already colored and directed are the inner edges of $C \setminus B$.

* for each inner vertex $v$ of $C \setminus B$, all edges incident to $v$ are colored and directed in such a way that the Schnyder rule (Figure 2.7(c)) is satisfied;

<figure><img src="image_20.png" /><figcaption>Figure 2.13: Invariant</figcaption></figure>
* every inner vertex $v \in B$ has exactly one outgoing edge $e$ in $C \setminus B$; and this edge has color 2. Let $v_r$ be the right neighbor and $v_l$ the left neighbor of $v$ on $B$, looking toward $T \setminus C$. Then all edges strictly between $(v, v_r)$ and $e$ in cw order around $v$ are ingoing of color 1 and all edges strictly between $e$ and $(v, v_l)$ in cw order around $v$ are ingoing of color 0.

These invariants are easily checked to be satisfied all along the procedure (see [Breoo] for a detailed presentation), which yields the following result:

**Lemma 2.7 (Brehm [Breoo])** Let us consider a plane triangulation $\mathcal{T}$ with root face $(V_0, V_1, V_2)$. Then the algorithm described above computes a Schnyder wood of $\mathcal{T}$ and can be implemented to run in time $O(n)$.

Finally, observe that the incremental algorithm described above actually computes a canonical ordering of the input triangulation: it suffices to consider the sequence of vertex shellings in reverse order.

**MINIMAL (MAXIMAL) SCHNYDER WOOD.** Note that a triangulation $\mathcal{T}$ can have many different Schnyder woods (as shown by Brehm [Breoo], the set of Schnyder woods of $\mathcal{T}$ forms a distributive lattice). Furthermore, the same Schnyder wood can be obtained from many different canonical orderings for the above-described traversal procedure.

As one can observe, at each step there are many choices among the possible free vertices on $B$, which possibly leads to many distinct Schnyder woods. Among all Schnyder woods, the minimal (resp. maximal) one plays an important role in many algorithmic and combinatorial problems. A fundamental property is that the minimal (resp. maximal) Schnyder wood has no ccw (resp. cw) oriented cycles of directed edges. The computation of the minimal (resp. maximal) Schnyder wood can be performed as before: at each step just perform the conquest of the free vertex $v$ on $B$ that is the closest to $V_0$ (resp. to $V_1$).

**COMPUTING SCHNYDER WOODS VIA EDGE CONTRACTIONS.** The algorithm originally proposed in [Sch90] for computing Schnyder woods was relying on a slightly different approach based on edge contractions.

An edge $(u, v)$ is *contractible* if $u$ and $v$ have exactly two common neighbors (no separating triangle containing $u$ and $v$): observe that contracting an edge $(u, v)$ of a plane triangulation $\mathcal{T}$ leads to a new smaller triangulation $\mathcal{T}'$ (as illustrated in the sequence of left picture in Fig. 2.14).

A crucial observation is that for a plane triangulation $\mathcal{T}$ with root face $(V_0, V_1, V_2)$ having at least 4 vertices it is possible to find a contractible inner edge $(V_2, v)$: this leads to construct a sequence of edge contractions that incrementally simplify the original triangulation until we are left with 3 vertices.

Then a Schnyder wood of $\mathcal{T}$ can be obtained by performing a sequence of *expansions*, accordingly to the sequence of edge contractions (in reverse order): the arguments underlying the validity of this procedure can be found in [Breoo] and [NR04].

**PRACTICAL IMPLEMENTATIONS.** It is worth nothing that in the planar case the algorithm based on vertex shellings and the procedure based on edge contractions are essentially equivalent: for instance they both allows us to recover all Schnyder woods of a given plane triangulation. Nevertheless, although they lead both to linear running time, there is no doubt that

Among the applications of canonical orderings we would like to mention an elegant linear-time algorithm for recognizing and embedding maximal planar graphs [NSI04]: its simplicity relies on the fact that in the triangular case the computation of a canonical ordering only requires the graph structure, since prior knowledge on the embedding is not needed. To detect free vertices it is actually sufficient to maintain the set $S_B$ of vertices having a neighbor already removed, and to chose a vertex with exactly two neighbors on $S_B$.

<figure><img src="image_21.png" /><figcaption>Figure 2.14: Computation of Schnyder woods via edge contractions.</figcaption></figure>

As we will see in the Chapter 3 the non planar case is much more involved: the approach based on vertex shellings and the one using edge contractions lead to distinct generalizations of Schnyder woods, each preserving some, but not all, the structural properties of Schnyder woods.
<figure><img src="image_22.png" /><figcaption>(random triangulations)</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Figure 2.15: Runtime cost of the incremental shelling algorithm for the computation of Schnyder woods and canonical orderings. Timings are expressed in seconds as a function of the size (millions of vertices). We plot the average timing costs over 100 executions, obtained allocating 6GB of RAM for the JVM (results are taken from [CD18]).</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Figure 2.16: Illustration of the *half-edge* data structure: each half-edge stores three references towards its previous, next and opposite half-edges and the target vertex, while each vertex stores a reference to an incoming incident half-edge. If one does not need to represent faces explicitly, this amounts to an overall storage of $2 \cdot 4e + n$ references for encoding a polygon mesh with $e$ edges and $n$ vertices. In the case of triangulations (assuming that the genus and the boundary size are small when compared to $n$), in its minimal form where we discard the previous half-edge, the storage cost of *half-edge* decreases to $3e + n = 18n + n$.</figcaption></figure>

the vertex shelling approach is simpler to implement and much faster in practice. While performing vertex shellings only requires to maintain a simple boundary cycle, the computation of edge contractions requires to deal with a dynamic data structure for triangulations or to simulate the local updates in a non-trivial way.

Once an efficient representation of combinatorial maps is provided (we make use of a Java implementation of the *half-edge* data structure, described in next section), the computation of Schnyder woods and canonical orderings via vertex shellings is extremely fast. As observed in practice on large inputs, for both real-world and random triangulations, our Java implementation allows processing between 5.95M and 8.62M vertices per second (see Fig. 2.15).

## 2.3 IMPLEMENTATIONS AND EXPERIMENTAL SETTINGS

The relevance of surface maps for application domains such as computational geometry, geometry modelling and computer graphics relies on the fact that surface meshes are among the most common representations of 3D shapes. A *polyhedral 3D mesh* is a collection of polygonal faces that define a discrete approximation of a surface. Most of times 5 people focus on *manifold* triangle meshes (all faces having degree 3), for which every edge is bounding either one or two triangles, and where the faces incident to a same vertex define a closed or open fan.

The *connectivity* of triangle meshes describes incident relations between mesh elements and corresponds to the combinatorics of triangulations embedded on orientable surfaces (simple maps, with no loops nor multiple edges). Assuming that the genus and the number of boundary edges is negligible when compared to the number $n$ of vertices, the number $m$ of faces is roughly equal to $2n$.

### COMMON MESH REPRESENTATIONS.
Most of the time mesh representations are implemented in the explicit pointer-based form, where references (or pointers) are used to describe incidence relations between mesh elements and navigation is performed throughout address indirection. One example is the popular *half-edge data structure* that falls within this framework: its implementation [Ket99] provides the representation of combinatorial maps offered by the CGAL library. As illustrated by the example in Fig. 2.16 each edge $e$ is represented as a pair of half-edges (with opposite directions), each associated to the two faces sharing $e$. In order to represent the combinatorics of the mesh each half-edge $h$ stores some information, namely: a reference to the target vertex, a reference to the opposite half-edge together with two references to the half-edges that follow and precede $h$ in ccw order in the face associated to $h$. Each vertex stores a reference to an incoming incident edge and, when needed, faces can be represented storing a reference to an incident half-edge.

Sometimes, when dealing with triangular meshes, an alternative solution can be preferred. For instance, face-based representations [Boi+02] support navigational operators equivalent to the ones offered by the half-edge data structure while using smaller memory resources: one only stores 6 references per triangle (3 references for incident vertices, and 3 references for the three neighboring faces), plus one reference per vertex (describing the map

<footnote n="5">5 For instance, more than 70% of the geometric datasets made available by the aim@shape repository are 3D polygonal meshes (about 84% of which are manifold).</footnote>
<figure><img src="image_25.png" /></figure>

<table><caption>Table 1: The table above reports the statistics for some of the real-world and synthetic graphs tested in this work: for large graphs (n ≥ 50k) the values of the diameter are approximated. Last column reports the diameter normalized with respect to the number of vertices. The top charts report some vertex degree distributions: most regular graphs appear leftmost.</caption><thead><tr><th>Real-world<br>3D meshes</th><th>vertices</th><th>faces</th><th>d<sub>6</sub></th><th>diam</th><th>diameter<br>normalized</th><th>Synthetic and<br>random graphs</th><th>vertices</th><th>faces</th><th>d<sub>6</sub></th><th>diam</th><th>diameter<br>normalized</th></tr></thead><tbody><tr><td>Egea</td><td>8268</td><td>16K</td><td>0.25</td><td>59</td><td>0.64</td><td>Stacked</td><td>88576</td><td>177K</td><td>0.222</td><td>8</td><td>0.026</td></tr><tr><td>Bunny</td><td>26002</td><td>52K</td><td>0.50</td><td>142</td><td>0.88</td><td>Globe</td><td>160002</td><td>320K</td><td>0.999</td><td>383</td><td>0.946</td></tr><tr><td>Aphrodite</td><td>46096</td><td>92K</td><td>0.45</td><td>229</td><td>1.06</td><td>Sphere</td><td>163842</td><td>327K</td><td>0.994</td><td>400</td><td>0.999</td></tr><tr><td>Iphigenia</td><td>49922</td><td>99K</td><td>0.38</td><td>200</td><td>0.89</td><td>Delaunay</td><td>100003</td><td>200K</td><td>0.294</td><td>138</td><td>0.43</td></tr><tr><td>Chinese Dragon</td><td>655980</td><td>1.3M</td><td>0.824</td><td>601</td><td>0.74</td><td>Random</td><td>100002</td><td>200K</td><td>0.116</td><td>78</td><td>0.24</td></tr></tbody></table>

from vertices to faces). According to Euler formula, this leads to a storage cost of 13 references per vertex (rpv).

Both edge-based and face-based mesh data structures fully support local navigation allowing us to efficiently implement most geometry processing algorithms: the code provided in Fig. 2.17 illustrates how to turn around a vertex in order to compute its degree.

**IMPLEMENTATIONS.** All experimental results (and graph layouts) presented in this manuscript are obtained with our implementations of the algorithms and data structures developed in our works.<fnref n="6" /> In particular, I have written Java implementations of mesh data structures (half-edge, winged-edge, triangle-based) and algorithms for graph drawing and graph encoding described in Chapters 4 and 5. All our tests are run on an HP EliteBook, equipped with 8GB of RAM and an Intel Core i7 2.60GHz, running under linux (Ubuntu 16.04) and with Java 1.8 64-bit.

**DATASETS.** We performed tests on a wide collection of graphs, whose sizes range from a few hundreds to millions of vertices. Our tests involve various kinds of datasets, including

```
Degree(v) {
  // Enumerating edges incident to v
  e = v.halfedge;
  d = 0;
  h = e.next.opposite;
  while (h!=e) {
    h = h.next.opposite;
    d = d + 1;
  }
  return d + 1;
}
```

<caption>Figure 2.17: Computation of the vertex degree using the half-edge data structure.</caption>

<footnote n="6">6 Pure Java implementations of our algorithms and data structures, as well as input graphs, are available at www.lix.polytechnique.fr/~amturing/software.html.</footnote>
* several real-world 3D meshes used in geometry processing: they are made available by the aim@shape and Thingi10k [ZJ16] repositories;

* planar random triangulations <fnref n="7" /> generated with our implementation of the uniform random sampler by Poulalhon and Schaeffer [PS06];

* stack triangulations;

* Delaunay triangulations of random points in the plane;

* synthetic regular graphs with different shapes (sphere, cylinder, ...).

As done in geometric processing, we use the proportion of degree 6 vertices, denoted by $d_6$, to measure the regularity of a graph: $d_6$ is close to 1 for regular meshes, while is sometimes below 0.3 for irregular 3d models. The proportion of degree 6 vertices can be even much smaller for some special classes of graphs. For instance in the case of random planar triangulations the distribution of vertex degrees follows an exponential decay: as evaluated in [Lis99; Goto3], the probability of having a vertex of degree i in a large random planar triangulation, as n goes to infinity, is $p_i = \frac{16(i-2)}{i} \binom{2i-2}{i-1} (\frac{3}{16})^i$ (as confirmed in our experiments, the proportion of degree 6 vertices in a large random triangulation is approximately 11.6%).

<footnote n="7">7 By random planar triangulation we mean here a simple triangulated planar map randomly chosen according to uniform distribution among all triangulations of size n. Observe that such random triangulations only satisfy topological planarity constraints, with no consideration of geometry: they are somehow pathological triangulations, being quite far for instance from Delaunay triangulations of random points in a planar domain.</footnote>
3.1 DEALING WITH HIGHER GENUS GRAPHS

It is worth noting that moving from the plane to higher genus surfaces, some of the beautiful properties of Schnyder woods might be lost. In principle a simple counting argument suggests that in genus 1 one could endow a triangulation with a 3-orientation (each vertex having outdegree 3). But unfortunately the correspondence between 3-orientations and Schnyder woods is no longer valid: the local Schnyder condition could be violated at some vertices, as illustrated in Fig. 3.1. And even when a 3-orientation yields an edge coloring satisfying the Schnyder local condition everywhere, there are examples for which the edges of the same color may form many disjoint circuits (see Fig. 3.2).

So, being conscious that something could be missed, we made some com-
promises: our definition [CAFL09] was aimed to preserve the global span-
ning condition even in higher genus. While we are not able to guarantee that
the local Schnyder condition is satisfied everywhere, the number of excep-
tions is still a small constant when the genus is bounded. Our definition of
Schnyder woods relies on an algorithmic approach, namely the correspon-
dence between the computation of Schnyder woods and canonical orderings:
this makes our construction quite simple to implement having the advan-
tage to work for any genus $g$ triangulated surface. It is worth noting that
until very recently most existing works were only dealing with the genus 1
case [GL14; DGL17].

DISCLAIMER. The contributions of this chapter are originated from the collaborations with O. Devillers, É. Fusy and T. Lewiner [CAFL09; CDF18b].

PLANARIZING THE GRAPH. A possible intuitive solution to deal with Schnyder woods in higher genus would consist in performing a planarization of the surface. Nevertheless we must pay attention on how the planarization works, especially if one aims to preserve the local Schnyder condition (almost) everywhere: observe that we have to deal with boundaries of arbitrary size, since non-trivial cycles can be of size $\Omega(\sqrt{n})$ and cut-graphs are of size $O(gn)$, as already mentioned in Section 2.1.2.

As far as we know the first attempt to makes use of Schnyder woods in
the non planar case is due to Bonichon, Gavoille, and Laboure [BGL05]:
their goal is to compute in linear time a partition of the edges into three
edge-disjoint spanning trees plus at most 3 edges. Their solution, working
in the genus 1 case relies on the computation of a tambourine (recall its
definition given in Section 2.1.2): cutting along two parallel non contractible
cycles we produce a tambourine plus a graph planar H that can thus be
endowed with a Schnyder wood. It thus only remains to assign colors to the
edges of the tambourine while avoiding cycles, which leads to the desired
forest decomposition. Unfortunately, as pointed out by the authors, the local
conditions of Schnyder woods are possibly not satisfied for a large number
of vertices, because the size of the tambourine might be arbitrary large. We

<figure><img src="image_26.png" /><figcaption>Figure 3.1: (top) A 3-orientation of a simple toroidal triangulation $T$ with 9 vertices. (bottom) The corresponding edge coloring does not satisfy the local Schnyder condition everywhere. It suffices to propagate the edge coloration starting from vertex 0 and check that the incoming edges at vertex 1 do violate the local Schnyder condition (all incoming edges in the same sector should have the same color). Among all the 9360 existing 3-orientations of $T$, only 2344 yield an edge coloring which is valid everywhere.</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>Figure 3.2: A 3-orientation whose corresponding edge coloring satisfies the local Schnyder condition at each vertex: the spanning condition is lost, since black edges define three disjoint cycles.</figcaption></figure>
<figure><img src="image_28.png" /><figcaption>Figure 3.3: A toroidal triangulation endowed with a g-Schnyder wood (the root-face is green). For g = 1 there are two special edges, each of which is doubled and delimits a 2-sided face. In this example special edges are of same color.</figcaption></figure>

point out that for toroidal graphs a different planarization approach has
been later proved to be suitable in the triangular (simple) toroidal case: the
elegant solution proposed by Gonçalves and Lévêque [GL14], satisfying the
local Schnyder condition at each vertex, will be sketched in Section 3.4.

Let us observe that, for both methods above, it is not clear how to get a
generalization to the case of genus $g \ge 2$.

3.2 g-SCHNYDER WOODS FOR TRIANGULATIONS OF ARBITRARY GENUS

3.2.1 *The definition*

Let us consider a genus g simple triangulation J with n vertices, having a
root-face f = (V₀, V₁, V₂) (the vertices are ordered according to a walk along
f with the interior of f on the right). We propose the following definition (il-
lustrated by Figures 3.3 and 3.4) of Schnyder woods that extends to arbitrary
genus the notion known in the planar case (recall Definition 2.3):

**Definition 3.1 (Castelli Aleardi, Fusy, and Lewiner [CAFL09])** Let us denote by $E^{\text{in}}$ the set of inner edges of $\mathcal{T}$. A g-Schnyder wood of $\mathcal{T}$ is a partition of $E^{\text{in}}$ into a set of normal edges and a set $E^s$ of special edges considered as fat, i.e., each special edge is doubled into two edges delimiting a face of degree 2, called a special face. In addition, each edge, a normal edge or one of the two edges of a special edge, is directed and has a label in $\{0,1,2\}$, so as to satisfy the following conditions:

*   **root-face condition:** The outer vertex $V_2$ is incident to no special edges. All inner edges incident to $V_2$ are ingoing of color 2.

Let $k \ge 0$ be the number of special edges incident to $V_0$ (each of these special edges is doubled), and let $L = (e_1, f_1, e_2, f_2, \dots, e_r, f_r)$ be the cyclic list of edges and faces incident to $V_0$ in ccw order ($f_i$ is the face incident to $V_0$ between $e_i$ and $e_{(i+1) \bmod r}$). A sector of $\nu$ is a maximal interval of $L$ that does not contain a special face nor the root-face. Note that there are $k+1$ sectors, which are disjoint; the one containing the edge $\{V_0, V_1\}$ is called the root-sector.

Then, all inner edges in the root-sector are ingoing of color 0. In all the other k
sectors, the edges in ccw order are of the form

$$
\mathrm{Seq}(\mathrm{In}1), \mathrm{Out}0, \mathrm{Seq}(\mathrm{In}2), \mathrm{Out}1, \mathrm{Seq}(\mathrm{In}0).
$$

The definitions of sectors and conditions are the same for $V_1$, except that all edges in the root-sector are ingoing of color 1.
* **local condition for inner vertices:** Every inner vertex $v$ has exactly one outgoing edge $e$ of color 2. Let $k$ be the number of special edges incident to $v$ (each of these edges is doubled and delimits a special face), and let us consider the cyclic list $L = (e_1, f_1, e_2, f_2, \dots, e_r, f_r)$ of edges and faces incident to $v$ in ccw order. A sector of $v$ is a maximal interval of $L$ that does not contain a special face nor the edge $e$. Note that there are $k+1$ sectors around $v$, which are disjoint (see Fig. 3.4 for an illustration).

Then, in each sector the edges in ccw order are of the form

$$ \mathrm{Seq}(\mathrm{In}1), \mathrm{Out}0, \mathrm{Seq}(\mathrm{In}2), \mathrm{Out}1, \mathrm{Seq}(\mathrm{In}0). $$

* **Cut-graph condition:** The graph $T_2$ formed by the edges of color 2 is a tree spanning all vertices except $V_0$ and $V_1$, and rooted at $V_2$, i.e., all edges of $T_2$ are directed toward $V_2$. The embedded subgraph $G_2$ formed by $T_2$ plus the two edges $(V_0, V_2)$ and $(V_1, V_2)$ plus the special edges (not considered as doubled here) is a cut-graph of $T$, which is called the cut-graph of the Schnyder wood.

(Note that the cut-graph condition forces the number of special edges to be $2g$.)

**REMARKS.** Note that if an inner vertex $v$ is incident to no special edge, then there is a unique sector around $v$, which is formed by all edges incident to $v$ except the outgoing one of color 2: the definition above implies that the edges around $v$ the local Schnyder condition as in the planar case. Since at most $4g$ vertices are incident to special edges, our definition implies that in fixed genus, almost all inner vertices satisfy the same local condition as in the plane. In addition the vertices incident to special edges satisfy a local condition similar to the one in the planar case.

### 3.2.2 Existence of g-Schnyder woods

The difficulty of extending combinatorial constructions to higher genus is due to the fact that some fundamental properties, such as the Jordan curve theorem, hold only in the planar case (genus 0). Following the approach suggested in [Lop+03; LLTo3], based on Handlebody theory for surfaces, we design a new shelling algorithm for higher genus surfaces: as in the planar case, our strategy consists in conquering the whole graph incrementally.

We use an operator conquer similar to the conquest of a free vertex used in the planar case (described in Section 2.2.2), as well as two new operators—split and merge—designed to represent the handle attachments that are necessary in higher genus. Our traversal strategy is expressed in terms of subcomplexes: a short overview of the required terminology is provided below (for more details we refer to [CAFL09]).

**SUBCOMPLEXES.** Given a map $M$ on a surface $S$, with $V$, $E$, and $F$ the sets of vertices, edges, and faces of $M$, a *subcomplex* $C = (V', E', F')$ of $M$ is given by subsets $V' \subset V$, $E' \subset E$, $F' \subset F$ such that the edges around any face of $F'$ are in $E'$ and the extremities of any edge in $E'$ are in $V'$. Note that a connected subcomplex $C$ of $M$ naturally inherits from $M$ the structure of a combinatorial map: it is then possible to define the notions of duality, Euler characteristic and facial walks for connected subcomplexes, as done for maps in Section 2.1.1. Facial walks are called *boundary walks* for $C$ when they do not correspond to a facial walk of a face in $F'$. A boundary brin is a brin $h$ in a boundary walk, and the corresponding *boundary corner* of $C$ $b = (h, h')$ is the pair formed by $h$ and the next brin $h'$ in $C$ in cw order

<figure><img src="image_29.png" /><figcaption>Figure 3.4: Local condition around special edges. (a) inner vertex incident to 2 special edges: there are 3 sectors delimited by the special edges and the outgoing edge of color 2. (b) inner vertex incident to one special edge: there are two sectors delimited by the outgoing edge of color 2.</figcaption></figure>

*Remark:* The last condition, stating that $T_2$ is a tree, is redundant in the planar case (it is implied by the local conditions) but not in higher genus: it is possible to find examples where all local conditions are satisfied but the edges of color 2 form many disjoint circuits.

<figure><img src="image_30.png" /><figcaption>Figure 3.5: (top) Result of a conquer operation on a free corner incident to $w$ and (bottom) a contractible chordal edge $(w, u)$ (illustrated in the toroidal case).</figcaption></figure>
around the origin v of h. Note that a boundary corner of C is not a corner of M if there are brins h₁, ..., hₖ of M \ C in cw order strictly between h and h'.

**CHORDAL EDGES AND FREE BOUNDARY CORNERS.** A chordal edge is an edge of $\mathcal{T} \setminus C$ whose two brins $h_1$ and $h_2$ are exterior brins of some boundary corners $b_1$ and $b_2$. A boundary corner $b$ of $C$ is free if no exterior edge of $b$ is a chordal edge. A chordal edge $e$ for $C$ is said to be separating if its dual edge $e^*$ is a bridge of the dual complex $D$ (a bridge is an edge whose removal disconnects the graph). Otherwise it is called non-separating.

**HANDLE OPERATORS.** Given a free boundary corner of $C$, performing conquer($b$) consists in adding to $C$ all exterior faces of $\mathcal{T}$ incident to $b$, as well as the edges and vertices incident to these faces (the effect of conquer($b$) is illustrated in Figure 3.9). Observe that $D$ remains connected after the conquest and the number of boundary faces of $C$ is unchanged, as well as the Euler characteristic: indeed, if the number of faces transferred to $C$ is $k$, then the number of vertices transferred to $C$ is $k-1$ and the number of edges transferred to $C$ is $2k-1$.

**Definition 3.2** A split edge for $C$ is a non-separating chordal edge $e$ such that the two brins of $e$ are incident to boundary corners in the same boundary face of $C$.

Observe that given a split edge $e$ its dual edge $e^*$ is not a bridge but has the same boundary face (of $D$) on both sides. The second operation, called split, is acting on a split edge $e$ as follows: double $e$ into two parallel edges delimiting a face $f$ of degree 2, and add the face $f$ and the two edges representing $e$ to $C$. Note that $D$ remains connected since $e^*$ is not a bridge. When doing the split operation, the boundary walk at the two extremities of $e$ is split into two boundary walks. Therefore the number of boundary faces of $C$ increases by 1. Note that the Euler characteristic $\chi(C)$ decreases by 1; indeed in $C$ the number of vertices is unchanged, the number of edges increases by 2 (addition of the split edge, which is doubled) and the number of faces increases by 1 (addition of the special face). And the Euler characteristic of the map $M$ associated with $C$ is unchanged (when including the boundary faces, the number of faces both increases by 2, as the number of edges), hence the genus of $M$ is also unchanged.

**Definition 3.3** A merge edge for $C$ is a chordal edge having its two brins incident to boundary corners in distinct boundary faces of $C$.

Observe that given a merge edge $e$, the faces of $D$ on both sides of its dual $e^*$ are distinct boundary faces, hence $e^*$ cannot be a bridge of $D$, i.e., $e$ is non-separating. We can now define the third operation, merge, related to a merge edge $e$: double $e$ into two parallel edges delimiting a face $f$ of degree 2, and add the face $f$ and the two edges representing $e$ to $C$. Note again that $D$ remains connected since $e^*$ is not a bridge. When doing a merge operation, the boundary faces at the two extremities of $e$ are merged into a single boundary face, so that the number of boundary faces of $C$ decreases by 1. Similarly as for a split operation, the Euler characteristic $\chi(C)$ decreases by 1 (addition of a doubled special edge and of one special face); and the Euler characteristic of the map $M$ associated with $C$ decreases by 2 (when including the boundary faces, the number of faces is unchanged, and the number of edges increases by 2), hence the genus of $M$ increases by 1.

The first operator, called conquer, process free boundary corners, not modifying the topology of C.

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

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

Figure 3.6: The result of a split operation on a split edge (w, u) (illustrated in the toroidal case). The boundary walk containing the extremities of (w, u) is split into two boundary walks (yellow and orange curves).

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

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

Figure 3.7: The result of a merge operation on a merge edge (w, u) (illustrated in the toroidal case). Informally a merge can be viewed as an operation that "adds a handle" to the subcomplex C.
<figure><img src="image_35.png" /><figcaption>Figure 3.9: Illustration of the colorient operations. Any split (or merge) edge (u, w) can be directed in one or two directions, depending on the traversal order on its extremities (we denote by $b_w$ a boundary corner incident to vertex w).</figcaption></figure>

A SHELLING ALGORITHM IN ARBITRARY GENUS We can now describe an algorithm for computing a g-Schnyder wood that naturally extends to any genus the shelling procedure by Brehm and sketched in Section 2.2. Its the pseudo-code is given in Fig. 3.8 and Fig. 3.10 shows a complete execution of the algorithm in the toroidal case.

As in the planar case, the traversal is a greedy sequence of conquest operations, with here the important difference that these operations are interleaved with 2g merge/split operations. Another point is that, in higher genus, the region that is grown is more involved than in the planar case (recall that in the planar case, the grown region is delimited by a simple cycle). It also turns out that a vertex might appear several times on the boundary of the grown complex, therefore we have to use the refined notion of free boundary corner, instead of free vertex in the planar case (in the planar case, a vertex appears just once on the boundary of the grown region).

Let us now give the precise description of the traversal procedure on a rooted triangulation of genus g. As in the planar case, we grow a "region" C. Precisely, C is a connected subcomplex all along the traversal. Initially, C is the root-face {$V_0, V_1, V_2$}, together with the edges and vertices of that face; at the end, C is equal to $\mathcal{T}$. We make use of the operation conquer(b) (with b a free boundary corner of C) and of the associated colorient rule, similar to the operation for free vertices described in Section 2.2.2 (for the planar case). More precisely, given a free boundary corner b of C, the operation colorient(b) proceeds as follows: let v be the vertex incident to b, and let e, $e'$ be the two edges delimiting b, with $e'$ after e in cw order around v. Orient e and $e'$ outward of v, giving color 1 to e and color 0 to $e'$. Orient all the exterior edges of b toward v and give color 2 to these edges (these edges are strictly between e and $e'$ in cw order around v).

The algorithm, as illustrated by the pseudo-code in Fig. 3.8, performs a sequence of handle operations split and merge to deal with topology changes, interleaved with a sequence of conquer+colorient operations (corresponding to a vertex shelling of the subcomplex $\mathcal{T} \setminus C$).

Observe the subtlety that, for positive genus, the vertices incident to merge or split edges have several corners that are conquered, as illustrated in Figure 3.9. Precisely, for a vertex v incident to $k \ge 0$ merge/split edges, its conquest occurs $k+1$ times if v is an inner vertex and k times if $v \in \{V_0, V_1\}$.

Note also that, when the algorithm terminates, the number of merge edges must be g and the number of split edges must be g. Indeed, in the initial step, C has $k=1$ boundary face and genus $g'=0$, while (just before) the last step C has $k=1$ boundary face and genus $g'=g$. Since the effect of each split is {$k \leftarrow k+1, g' \leftarrow g'$} and the effect of each merge is {$k \leftarrow k-1, g' \leftarrow g'+1$}, there must be the same number of splits as merges

// $\mathcal{T}$ a simple triangulation of genus g
computeSchnyderAnyGenus(\mathcal{T}) {
  Set C as the root-face $f = (V_0, V_1, V_2)$;
  while (C ≠ \mathcal{T}) {
    find an update-candidate $\sigma$ for C;
    If $\sigma$ is a free boundary corner b
      conquer(b); colorient(b);
    If $\sigma$ is a merge edge $e = \{u, w\}$ for C
      merge(u, w);
    If $\sigma$ is a split edge $e = \{u, w\}$ for C
      split(u, w);
  }
}

<caption>Figure 3.8: Computation of g-Schnyder woods. An *update-candidate* for C is either a free boundary corner, or a split edge, or a merge edge. Note that the above algorithm performs conquests, merge operations and split operations in whichever order, i.e., with no priority on the 3 types of operations.</caption>
<figure><img src="image_36.png" /><figcaption>Figure 3.10: Execution of our traversal algorithm on a toroidal triangulation with 9 vertices. (a) The traversal starts with a conquest at the outer vertex $V_2 = v_7$. The area explored (white triangles) is homeomorphic to a disk. (b) Whenever there remain no free corners, conquer operations cannot be performed: thus it is possible to find a split edge (light blue edge). We then perform the conquest of a free corner (c) until we get stuck. We look for a merge edge: after the merge operation the region $\mathcal{T} \setminus C$ becomes a topological disk (d), the traversal can be completed with a sequence of conquer operations (e)-(m).</figcaption></figure>

(for $k$ to be the same finally as initially) and the number of merges must be $g$ (for $g'$ to increase from 0 to $g$).

The algorithm described above terminates computing an edge coloring and orientation that satisfies almost everywhere the local Schnyder condition: observe that the $2g$ merge and split edges processed by our shelling procedure are precisely the special edges involved in Definition 3.1. This leads to our main result:

**Theorem 3.4 (Castelli Aleardi, Fusy, and Lewiner [CAFL09])** Any simple triangulation $\mathcal{T}$ of genus $g$ with $n$ vertices admits a $g$-Schnyder wood, which can be computed in time $O((n+g)g)$.

The termination relies on the fact that we can always find a candidate (a conquer or handle operation) at each step of the shelling procedure: in particular we look at candidates incident to the boundary face $f_0$ of $C$ containing the root edge $(V_0, V_1)$. Intuitively, if the vertex shelling phase get stuck at some step (no free boundary corners to conquer), then there exists a split or merge chordal edge $e$ having one of its extremities on $f_0$, and the algorithm can perform a split or merge operation. Observe that such an edge $e$ cannot be a separating chordal edge having its two extremities on $f_0$ otherwise it would enclose a planar region containing a free boundary corner of $C$ (which would lead to a contradiction).

For the analysis of the runtime complexity, let us assume that we perform a maximal sequence of conquer operations, until the algorithm get stuck not finding any free boundary corner (this phase can be performed in linear time, using the suitable data structures, as in the planar case). Then we have to look for a split edge whose dual edge $e^*$ is not a bridge of the dual complex: this requires linear time as well, as detecting all bridges in the dual
<figure><img src="image_37.png" /><figcaption>Figure 3.11: A toroidal triangulation endowed with a g-Schnyder wood. The edges of color 2 form a tree $T_2$, and the addition of the two special edges and the two outer edges incident to $V_2$ yields a cut-graph $G_2$. The edges of color 0 plus the two outer edges incident to $V_0$ form a spanning cellular subgraph $G_0$ with 3 faces (two faces are degenerated, having degree 2). Similarly, the edges of color 1 plus the two outer edges incident to $V_1$ form a spanning cellular subgraph $G_1$ with 3 faces.</figcaption></figure>

can be done in $O(|E|)$ time using the depth-first search principles of [Tar74].
Observe that this phase needs to be performed at most $O(g)$ times.

The validity of the edge coloring computed by our traversal relies on
some invariants on the colors and directions of the edges of a genus g trian-
gulation $\mathcal{T}$ that remain satisfied all along the traversal and ensure that the
computed structure is a g-Schnyder wood. The main difference between the
planar and higher genus case involves the extremities of the special edges:
observe that these edges can be considered as two parallel edges that de-
limit a face of degree 2. Special cases concern the sectors around $V_0$ and $V_1$
on the root face, which could be possibly be incident to some special edge
(for instance this occurs in the example of Fig. 3.11).

A detailed proof of the correctness and runtime complexity of the algo-
rithm above can be found in Sections 4.3 and 4.4 of [CAFL09].

3.2.3 Spanning properties of g-Schnyder woods

Finally, we point out that g-Schnyder woods give rise to decompositions
into 3 spanning cellular subgraphs, one with one face and the two other
ones with 1 + 2g faces. More precisely, let us consider a triangulation T
of genus g endowed with a g-Schnyder wood computed by the algorithm
COMPUTESCHNYDERANYGENUS. Let us define G₂ as the graph formed by
the edges of color 2, the two edges {V₁, V₂} and {V₀, V₂}, and the 2g special
edges (not considered as doubled). Let us define G₀ (resp. G₁) as the graph
formed by the edges of color 0 (resp. color 1) plus the outer edges incident
to V₀ (resp. incident to V₁): in this case we consider the special edges as
doubled (thus T gets 2g additional degenerated faces of degree 2).

**Proposition 3.5 ([CAFL09])** The graphs $G_0$, $G_1$ and $G_2$ defined above satisfy the following properties:

• $G_2$ is a cut-graph of $\mathcal{T}$;

* $G_0$ and $G_1$ are spanning cellular subgraphs of $\mathcal{T}$ with $1+2g$ faces (where some of the faces might be degenerated, of degree 2).

The properties of $G_2$ (cut-graph condition), and of $G_0$, $G_1$ stated above
can be considered as extensions of the fundamental property of planar
Schnyder woods [Sch89; Sch90]: in the planar case, for each color $i \in \{0, 1, 2\}$,
the graph formed by the edges in color $i$ plus the two outer edges incident
to $V_i$ is a spanning tree. Figure 3.11 shows an example in genus 1.
### 3.3 CANONICAL ORDERING FOR CYLINDRICAL SIMPLE TRIANGULATIONS

In this section we extend the notion of canonical ordering (classically studied on plane graphs) to cylindrical simple triangulations: we will explain in Section 5.3 how to make use of this tool for computing periodic drawings of toroidal graphs. An important observation must be made: we assume that the inner boundary $\Gamma_{\text{inn}}$ of the input triangulation is chord-free.

**Definition 3.6 (Castelli Aleardi, Devillers, and Fusy [CDF18b])** Let $G$ be a cylindrical simple triangulation with no chordal edge at $\Gamma_{\text{inn}}$. An ordering $\pi = \{v_1, \dots, v_n\}$ of the vertices of $G \setminus \Gamma_{\text{inn}}$ is called a canonical ordering if it satisfies:

* For each $k \in [0..n]$ the map $G_k$ induced by $\Gamma_{\text{inn}}$ and by the vertices $\{v_1, \dots, v_k\}$ is a cylindrical triangulation. The boundary outer face of $G_k$ is denoted $B_k$.

* For each $k \in [1..n]$, the vertex $v_k$ is on $B_k$, and its neighbours in $G_{k-1}$ are consecutive on $B_{k-1}$ (see Fig. 3.12).

The notion of canonical ordering makes it possible to construct a cylindrical triangulation $G$ incrementally, starting from $G_0 = \Gamma_{\text{inn}}$ and adding one vertex at each step. While in the planar case, one starts with $G_0$ being an edge, here one starts with $G_0$ being a cycle, seen as a cylindrical map with no internal face. The computation of such an ordering is done by a shelling procedure, similar to the one considered in Section 2.2.2. At each step the graph formed by the remaining vertices is a cylindrical triangulation, the inner boundary remains $\Gamma_{\text{inn}}$ all the way, while the outer boundary $B_k$ (initially $\Gamma_{\text{ext}}$) has its contour getting closer to $\Gamma_{\text{inn}}$. A vertex $v \in B_k$ is free if $v$ is incident to no chord of $B_k$ and if $v \notin \Gamma_{\text{inn}}$. The shelling procedure goes as follows, with $n$ the number of vertices in $G \setminus \Gamma_{\text{inn}}$:

for $k$ from $n$ to 1, choose a free vertex $v$ on $B_k$, assign $v_k \leftarrow v$, and then delete $v$ together with all its incident edges.

The existence of free vertices follows from the same argument as in the planar case [Bre00]. First, since there is no chord at $\Gamma_{\text{inn}}$, then as long as $B_k \neq \Gamma_{\text{inn}}$ there is at least one vertex on $B_k \setminus \Gamma_{\text{inn}}$. If there is no chord for $B_k$, then any vertex $v \in B_k \setminus \Gamma_{\text{inn}}$ is free. If there is at least one chord $e = \{u, v\}$ for $B_k$, let $P_e$ be the path connecting $u$ and $v$ on $B_k$ such that the cycle $P_e + e$ does not enclose the inner boundary-face in the annular representation, and let $d_e$ be the length of $P_e$ (note that $d_e \ge 2$). Let $e = \{u, v\}$ be a chord such that $d_e$ is smallest possible. Then any vertex in $P_e \setminus \{u, v\}$ is free. Since there exists a free vertex at each step, the procedure terminates as stated below:

**Proposition 3.7 (Castelli Aleardi, Devillers, and Fusy [CDF18b])** Any cylindrical simple triangulation $G$ with no chordal edge at $\Gamma_{\text{inn}}$ admits a canonical ordering that can be computed in linear time by a shelling procedure.

**UNDERLYING FOREST AND DUAL FOREST.** Given a cylindrical simple triangulation $G$ with no chordal edge at $\Gamma_{\text{inn}}$ endowed with a canonical ordering $\pi$, we define the *underlying forest* $F$ for $\pi$ as the oriented subgraph of $G$ where each vertex $v \in \Gamma_{\text{ext}}$ has outdegree 0, and where each $v \notin \Gamma_{\text{ext}}$ has exactly one outgoing edge, which is connected to the adjacent vertex $u$ of $v$ of largest label in $\pi$. The forest $F$ can be computed on the fly during the

We first defined the notion of cylindrical canonical orderings for cylindrical triangulations in [CDF12]: a generalization to essential 3-connected maps is given in [CDF18b].

<figure><img src="image_38.png" /><figcaption>Figure 3.12: From $G_{k-1}$ to $G_k$ in a canonical ordering for a cylindrical simple triangulation (annular representation, only the boundaries and next added vertex and added edges are shown).</figcaption></figure>

The linear time complexity of the shelling procedure is justified in [CDF18b]. This algorithm is rather simple to implement and fast in practice: as by-product this leads to efficiently compute toroidal Schnyder woods as illustrated in Section 3.4.3.
<figure><img src="image_39.png" /><figcaption>Figure 3.13: Shelling procedure to compute a canonical ordering of a cylindrical simple triangulation (at each step the next shelled vertex is surrounded). The underlying forest is computed on the fly; the last drawing shows the underlying forest superimposed with the dual forest.</figcaption></figure>

shelling procedure: when processing an admissible vertex $v_k$, for each neighbour $v$ of $v_k$ such that $v \notin B_k$, add the edge $\{v, v_k\}$ to $F$, and orient it from $v$ to $v_k$. Since the edges are oriented in increasing labels, $F$ is an oriented forest; it spans all vertices of $G$ and has its roots on $\Gamma_{\text{ext}}$. The augmented map $\hat{G}$ ($\hat{G}$ has to be seen as a map on the sphere) is obtained from $G$ by adding a vertex $w_1$ inside $B_{\text{inn}}$, a vertex $w_2$ inside $B_{\text{ext}}$, and connecting all vertices around $B_{\text{inn}}$ to $w_1$ and all vertices around $B_{\text{ext}}$ to $w_2$, thus triangulating the interiors of $B_{\text{inn}}$ and $B_{\text{ext}}$. We denote by $\hat{F}$ the forest $F$ plus all edges incident to $w_1$ and all edges incident to $w_2$. The dual forest $F^*$ for $\pi$ is defined as the graph formed by the vertices of $\hat{G}^*$ (the dual of $\hat{G}$) and by the edges of $\hat{G}^*$ that are dual to edges not in $\hat{F}$. Since $\hat{F}$ is a spanning connected subgraph of $\hat{G}$, $F^*$ is a spanning forest of $\hat{G}^*$. Precisely, each of the trees (connected components) of $F^*$ is rooted at a vertex "in front of" each edge of $\Gamma_{\text{inn}}$, and the edges of the tree can be oriented toward this root-vertex, see Fig. 3.13 bottom right. Each edge $e^*$ of $F^*$ is in a certain tree-component $T^*$ rooted at a vertex $V_0$ in front of a certain edge of $\Gamma_{\text{inn}}$. Let $P$ be the path from $e^*$ to $V_0$ in $T^*$; $P$ is shortly called the root-path of $e^*$.

### FROM CANONICAL ORDERINGS TO EDGE COLORING AND ORIENTATIONS.
Once we have a notion of canonical ordering for cylindrical triangulations we can easily get a partition of the edges (except the ones on $\Gamma_{\text{inn}}$) into three sets of oriented and colored edges. We proceed in the usual way, already

<figure><img src="image_40.png" /><figcaption>Figure 3.14: Coloring rule associated to the removal of a vertex $v$.</figcaption></figure>
described for the planar and genus g case, by defining a coloring rule that assigns colors and orientations to edges during the shelling process described above. This is better described by the statement below which is a by-product of Proposition 3.7:

**Corollary 3.8** Let G be a cylindrical simple triangulation with no chordal edge at $\Gamma_{\text{inn}}$. Then it is possible to compute in linear time an orientation and coloring of all edges in $G \setminus \Gamma_{\text{inn}}$ satisfying the following conditions:

* local condition for inner vertices: each inner vertex $v$ has exactly three outgoing edges (one for each color) and the edges incident to $v$ satisfy the local Schnyder condition as in the planar case;

* local condition for $\Gamma_{\text{ext}}$ (see right picture in Fig. 3.15): each vertex $v \in \Gamma_{\text{ext}}$ has exactly two outgoing edges (of color 0 and 1); moreover, all the edges between the right and left neighbors of $v$ on $\Gamma_{\text{ext}}$, are listed starting from $(v, v_r)$ to $(v, v_l)$ in cw direction around $v$ as follows:

$$ \text{Seq}(\text{In}0), \text{Out}1, \text{Seq}(\text{In}2), \text{Out}0, \text{Seq}(\text{In}1). $$

* local condition for $\Gamma_{\text{inn}}$ (see left picture in Fig. 3.15): each vertex $v \in \Gamma_{\text{inn}}$ has exactly one outgoing edge (of color 2), and all incident edges between $(v, v_l)$ and $(v, v_r)$ are listed in cw direction as follows:

$$ \text{Seq}(\text{In}1), \text{Out}2, \text{Seq}(\text{In}0). $$

Observe that the edges of color 2 define the underlying forest F described above. Similarly, the edges of color 0 and 1 define two forests spanning all vertices of G, whose connected components are ending at the vertices of $\Gamma_{\text{inn}}$ (as illustrated in the example of Fig. 3.16).

## 3.4 SCHNYDER WOODS FOR TOROIDAL TRIANGULATIONS

The first generalizations [BGL05; CAFL09] of Schnyder woods were motivated by applications involving graph encoding problems, aiming to preserve their global spanning properties. Since then the study of Schnyder woods for non planar graphs have attracted a lot of attention. This is particularly true in the toroidal case, for which some elegant generalizations led to several applications, ranging from graph drawing to bijective encodings.

### 3.4.1 The definition of Gonçalves and Lévêque [GL14] (for the triangulated case)

The key idea underlying the definition proposed by Gonçalves and Lévêque [GL14] is that Euler formula says that the number of edges is exactly $m = 3n$ on the torus. This means that in principle it could be possible to endow a triangulation with an edge orientation where, hopefully, every vertex satisfies the local Schnyder rule. So, in the toroidal case, the hope is to get rid of the special role of the three outer vertices lying on the root face, and to keep the symmetry of the underlying edge partition (observe that this symmetry is lost in the definition of g-Schnyder woods given in Section 3.2.1).

Finally, it turns out that a combinatorial structure satisfying the requirements above exists in the toroidal case, leading to the following definition<fnref n="1" /> illustrated in Fig. 3.17:

<figure><img src="image_41.png" /><figcaption>Figure 3.15: Local conditions for vertices on $\Gamma_{\text{inn}}$ (left) and vertices on $\Gamma_{\text{ext}}$ (right).</figcaption></figure>

<figure><img src="image_42.png" /><figcaption>Figure 3.16: A cylindrical triangulation endowed with an edge coloring/orientation according to Corollary 3.8.</figcaption></figure>

<footnote n="1">¹ Observe that the definition in [GL14] is more general and extends the notion of Schnyder woods for the 3-connected case.</footnote>
<figure><img src="image_43.png" /><figcaption>Figure 3.17: Toroidal Schnyder woods for simple triangulations satisfying the local Schnyder condition (T1) of Definition 3.9 around every vertex. (left) the edge orientation and coloring satisfies the crossing condition (T2) (but there are several disjoint mono-chromatic cycles). (right) Another edge coloring and orientation of the same triangulation: each color defines one mono-chromatic cycle, but the crossing condition (T2) is not satisfied.</figcaption></figure>

**Definition 3.9 (Gonçalves and Lévêque [GL14])** Let $\mathcal{T}$ be a toroidal triangulation. A Schnyder wood of $\mathcal{T}$ is an orientation and labeling, with labels in $\{0, 1, 2\}$ of the edges of $\mathcal{T}$ so as to satisfy the following condition:

* (T1) **local Schnyder condition (for all vertices):** For each vertex $v$, the edges incident to $v$ in counterclockwise (ccw) order are: one outgoing edge colored 2, zero or more incoming edges colored 1, one outgoing edge colored 0, zero or more incoming edges colored 2, one outgoing edge colored 1, and zero or more incoming edges colored 0;

The Schnyder wood is said to be crossing if it satisfies the further condition below

* (T2) **Crossing condition:** Every monochromatic cycle of color $i$ intersects at least one monochromatic cycle of color $i-1$ and at least one monochromatic cycle of color $i+1$.

The definition above is particularly elegant since it preserves the symmetry of the three colors, so there is a natural correspondence between a toroidal Schnyder wood and the underlying 3-orientation (up to a cyclic permutation of the colors). In principle the global spanning property of Schnyder wood is lost, since the edges of a same color could define a non-connected graph: as illustrated by left example in Fig. 3.17, the graph induced by one color could consist of several disjoint connected components, but it is possible to prove that each component contain exactly one directed cycle. More precisely, Gonçalves and Lévêque (see Theorem 7 in [GL14]) show that in a toroidal crossing Schnyder wood all mono-chromatic cycles of the same color are non-contractible and homotopic, and they do not intersect each other; so condition (T2) becomes even stronger, since one can show that every pair of mono-chromatic cycles $\Gamma_i$ and $\Gamma_j$ (for $i \neq j$) are not homotopic and must intersect.

The condition (T2) is particularly interesting, leading to several applications. For instance, this condition is crucial for obtaining a periodic grid drawing of toroidal triangulations that extends the region counting approach of planar Schnyder drawings [GL14]. Moreover, if one consider, for a given triangulation, the set of 3-orientations that correspond to crossing Schnyder woods then it is possible to define a distributive lattice structure similarly to the planar case (we refer to [KGL19] for more details).

Here we adopt the formulation for the triangulated case given in [DGL17]: observe that the crossing condition is included in the definition of toroidal Schnyder woods originally proposed in [GL14]
### 3.4.2 Existence of toroidal Schnyder woods

As shown in [GL14] it is possible to show the existence for the general case of essentially 3-connected toroidal maps making use of the approach based on edge contractions. The main idea is to perform a sequence of contractions until the resulting graph has few vertices: the Schnyder wood can be recovered by assigning colors after the edge expansions (in reverse order). The validity of this approach relies on very involved case analysis (observe that there are no special outer vertices in the definition of toroidal Schnyder woods): unlike planar Schnyder woods, in the toroidal case one has to distinguish many cases of edge contractions in order to preserve the structure of monochromatic cycles, which is a non local property. For the triangulated (simple) case there is another simpler proof, as sketched below.

**TOROIDAL SCHNYDER WOODS FOR SIMPLE TRIANGULATIONS.** For the case of simple triangulations (no loops and no multiple edges) Gonçalves and Lévêque [GL14] propose another proof of existence of toroidal Schnyder woods: it suffices to apply a planarization approach relying on Theorem 2.2.

The idea, illustrated in Fig. 3.18, consists to cut the input triangulation $\mathcal{T}$ along three non-contractible (and non-homotopic) cycles $\Gamma_0, \Gamma_1$ and $\Gamma_2$ sharing a common vertex $v$. As result one obtains a partition of the faces of $\mathcal{T}$ into two quasi-triangulations $G_1$ and $G_2$ which are internally 3-connected and have 3 copies of vertex $v$, denoted $V_0, V_1$ and $V_2$, on their boundaries. It is then possible to endow both $G_1$ and $G_2$ with a planar Schnyder wood, where all inner vertices satisfy the local Schnyder condition and the boundary edges have two opposite orientations (for more details please refer to [Felo1; Felo3]). Now it suffices to assign colors and orientations to the edges according to the following rule: assign color $i$ to a boundary edge appearing on the path $\Gamma_i$ (oriented toward $V_i$) for $i \in \{0, 1, 2\}$. As observed by Gonçalves and Lévêque [GL14], this ensures that after gluing together $G_1$ and $G_2$ the resulting edge coloring and orientation corresponds to a valid toroidal crossing Schnyder wood as stated below:

**Proposition 3.10 (Gonçalves and Lévêque [GL14])** Any simple toroidal triangulation $\mathcal{T}$ admits a toroidal crossing Schnyder wood. Moreover, such a Schnyder wood contains three monochromatic cycles (one for each color) all intersecting at one common vertex, while being pairwise disjoint otherwise.

Observe that the statement above does not guarantee that the edges of the same color form a connected graph: in principle the corresponding Schnyder wood could contain several parallel monochromatic cycles of the same color.

Unfortunately, as pointed out in [Lév16], it is not clear how to turn the procedure above into a linear-time algorithm (the preliminary step requires Theorem 2.2 which relies on a result involving disjoint paths by Robertson and Seymour [RS86]).

#### Open questions

As far as we know there are a few interesting questions concerning toroidal and higher genus Schnyder woods left open by [GL14; AGK16; KGL19] (see also [Lév16] for more details).

> "Does a simple toroidal triangulation admit a Schnyder wood such that there is just one monochromatic cycle per color?"

As far as we know there are no practical implementations of the procedure based on edge contractions for computing toroidal Schnyder woods, even for triangulations, for which the case analysis is much simpler. Observe that obtaining a linear-time implementation requires to choose contractible edges in a fast way (which is possible, but not trivial to implement).

<figure><img src="image_44.png" /><figcaption>Figure 3.18: Existence of toroidal Schnyder woods for simple toroidal triangulations [GL14].</figcaption></figure>
<figure><img src="image_45.png" /><figcaption>Figure 3.19: A few triangles meshes of genus 1 endowed with toroidal Schnyder woods satisfying condition (T1) of Definition 3.9. They have been obtained with our implementation of the shelling procedure described by Corollary 3.11.</figcaption></figure>

> "Moreover, can one require that monochromatic cycles all intersect on one vertex and they are pairwise disjoint otherwise?"

> Is it possible "to generalize the shelling order method for the torus"?

A further interesting open question involves the existence of generalized Schnyder woods for maps of arbitrary genus. A partial answer to this question has been very recently provided by Jason Suagee [Sua21] in its PhD dissertation: unfortunately the assumptions are quite strong, as the existence of generalized Schnyder woods is guaranteed only for triangulations having very large edge-width (refer to Section 6.1 for a few more details).

We will address some of the problems above, providing theoretical (Section 3.4.3) and experimental (Section 6.1) partial answers to these questions.

### 3.4.3 Our contribution: toroidal Schnyder woods via vertex shellings

It is interesting to observe that our incremental algorithm for computing canonical orderings of cylindrical triangulations can be turned into an efficient and simple procedure for computing toroidal Schnyder woods satisfying the condition (T1) of Definition 3.9.

**COMPUTING A NON-CONTRACTIBLE CYCLE.** We first compute a directed non-contractible cycle $\Gamma$ of the input (simple) toroidal triangulation $\mathcal{T}$ such as there are no chordal edges on the right side of $\Gamma$ (observe that we do not care about the length of this cycle). For instance, such a cycle can be derived by our shelling procedure described in Section 3.2.2. Just perform a sequence of conquer operations until a *split edge* $e = (u, v)$ is found. Then we can simply consider the two paths $\Pi_1(u) = \{u, \dots, a, \dots, V_2\}$ and $\Pi_2(v) = \{v, \dots, a, \dots, V_2\}$, where $a$ is the common ancestor of $u$ and $v$ in the tree $T_2$: because of the Schnyder local condition both paths are chord-free.

Assume that $v$ is preceding $u$ on the boundary of the conquered region (which is planar), i.e., $v$ is closer to vertex $V_0$. The cycle $\Gamma$ is obtained concatenating the subpath $\Pi'_1(u) = \{u, \dots, a\}$ with the subpath $\Pi'_2(v) = \{a, \dots, v\}$ (where we reverse the direction of the edges of $\Pi_2(v)$) and finally adding the edge $(v, u)$. As illustrated in Fig. 3.20, at the exception of $u$ and $v$ all vertices of $\Gamma$ are included in a planar region $C$ (whose boundary is a simple contractible cycle): the local Schnyder planar condition ensures that there are no chords on the right side of $\Gamma$ inside $C$. The only two vertices of $\Gamma$ appearing on the boundary of $C$ are $u$ and $v$: a chordal edge between them would yield to the existence of a multiple edge (a contradiction, as by assumption the input triangulation is simple). Observe that the cycle $\Gamma$ we

<figure><img src="image_46.png" /><figcaption>Figure 3.20: Computation of a non-contractible (oriented) cycle $\Gamma$ with no chordal edges on its right side.</figcaption></figure>
<figure><img src="image_47.png" /><figcaption>Figure 3.22: Computation of toroidal Schnyder woods via vertex shellings: the input toroidal triangulation is cut along a non contractible cycle $\Gamma$ with no chordal edges on one side (left picture), which allows us to compute a cylindrical canonical ordering (vertex labels reflect the shelling order). The resulting edge coloring (right picture) does not satisfy the crossing condition (T2): for instance there are two parallel cycles of color 0 and 2 that are not intersecting.</figcaption></figure>

obtained in this way is non-contractible since it is included in the cut-graph $G_2$ of $\mathcal{T}$ defined in Section 3.2.3.

### FROM CYLINDRICAL CANONICAL ORDERING TO TOROIDAL SCHNYDER WOODS.
Given a non-contractible cycle $\Gamma$ (with no chords on its right side) as described above we can planarize $\mathcal{T}$ cutting along $\Gamma$ obtaining a cylindrical triangulation $G$ whose inner inner $\Gamma_{\text{inn}}$ is chord-free: we can thus running our algorithm for cylindrical canonical orderings and endow $G$ with an edge coloring satisfying the constraints of Corollary 3.8. Let us consider the edge coloring and orientation of $\mathcal{T}$ obtained by gluing $\Gamma_{\text{inn}}$ and $\Gamma_{\text{ext}}$, where the edges of $\Gamma$ are naturally inheriting the edge coloring and orientation from $\Gamma_{\text{ext}}$. It is easy to see that we obtain a 3-orientation, as a simple by-product of Corollary 3.8. Moreover for every vertex $v \in \Gamma$ one can check that the edge coloring satisfies condition (T1) by distinguishing a few cases, depending on the colorations of edges incident to $v$: as illustrated in Fig. 3.21 after gluing the two boundary cycles $\Gamma_{\text{inn}}$ and $\Gamma_{\text{ext}}$ the local Schnyder condition is satisfied (all other vertices, not lying on $\Gamma$, satisfy the same condition as in the planar case).

**Corollary 3.11** Let $\mathcal{T}$ be a simple toroidal triangulation of size $n$. Then it is possible to compute in linear-time a Schnyder wood of $\mathcal{T}$ satisfying the condition (T1) for all vertices.

Unfortunately we have to point out that the edge coloring provided by Corollary 3.11 is not guaranteed to satisfy the condition (T2). There are examples computed by our algorithm such that the resulting Schnyder wood contains monochromatic cycles of different colors that are no intersecting: in the example of Fig. 3.22 there is a black cycle not intersecting any monochromatic red (it is actually parallel to another red cycle).

As one would expect the approach sketched above leads to a simple and very fast implementation: the pictures in Fig. 3.19 show a few triangle meshes of genus 1 endowed with a toroidal Schnyder wood. Let us mention that, to our knowledge, there are no existing implementations of the algorithms for computing toroidal Schnyder woods and higher genus 3-orientations described in [GL14; DGL17; AGK16; KGL19; Sua21].

<figure><img src="image_48.png" /><figcaption>Figure 3.21: Local condition for vertices on the non-contractible cycle $\Gamma$: every vertex has an outgoing edge of color 2 on the right side of $\Gamma$; the outgoing edges of color 0 and 1 are on the left side, possibly lying on $\Gamma$.</figcaption></figure>
The problem of encoding and representing graphs involves a broad spectrum of technics and applications, and has been addressed in the last four decades in several distinct domains including computational geometry, geometry processing and computer graphics, enumerative combinatorics, graph algorithms, data compression and complex networks.

The problem of encoding the combinatorics of graphs embedded on surfaces is part of the so-called *mesh compression problem*: we refer to the surveys by Alliez and Gotsman [AG05] and by Maglo et al. [Mag+15] that provide a comprehensive overview of the results developed in the geometry processing community. For the reader who is interested in the design of compact data structures and compression schemes dealing with more general classes of graphs (such as *complex networks*) we suggest the recent survey by Besta and Hoefler [BH18].

In this chapter we consider the problem of encoding and compactly representing graphs which are (locally) planar and we focus on works that make use of *tree-based decompositions*. In particular, the use of Schnyder woods and related combinatorial structures has led to the most efficient compression schemes and compact data structures provided with theoretical guarantees which are known so far.

The contributions of this chapter <fnref n="1" /> are originated from the collaborations with O. Devillers, É. Fusy and T. Lewiner [CAFL09; CFL10; CD18].

## 4.1 RELATED WORKS

### 4.1.1 Tree-based encodings

The use of spanning trees decompositions dates back to the pioneristic work of Turan [Tur84], who proposed a general way for efficiently representing the combinatorics of a planar graph with a linear number of bits. The idea is very simple (and illustrated on a small example in Fig. 4.1): given a planar graph $G$ with $n$ vertices one has just to chose any (arbitrary) spanning tree $T$ of $G$ and to encode the edges appearing both in $T$ and $G \setminus T$. Because of the planarity of $G$ and of its dual, $T$ and $G \setminus T$ can be both represented with two balanced parenthesis words whose size are roughly $2n$. Unfortunately, in order to recover from these two words the original graph $G$, the two encodings of $T$ and $G \setminus T$ must be interleaved. Thus we need a multiple parenthesis word (consisting of two types of open/closed parentheses) whose length is $2e$: this yields an encoding on ≈ $4e$ bits, since each edge is encoded by a pair of open/closed parenthesis (or brackets), and we need two bits to encode each of the 4 symbols. Planar triangulations can be thus encoded with at most $12n$ bits.

The framework proposed by Turan is quite general and thus not really efficient, at least when compared to the current state-of-the-art. Quite interestingly, as pointed out by Isenburg [IS05], many compression schemes de-

<figure><img src="image_49.png" /><figcaption>Figure 4.1: To encode a planar graph $G$ with $n$ vertices the Turan encoding [Tur84] makes use of an arbitrary spanning tree $T$ of $G$: both $T$ and $G \setminus T$ can be represented with balanced parenthesis words of size at most $2n$, obtained performing a ccw traversal of the contour of $T$ (rooted at vertex 0).</figcaption></figure>

<footnote n="1">¹ This chapter does not include my works [CDS05a; CDS05b; CDS08; CDM11; Bar+12] on the so-called *succinct representations* (sometimes referred to as *succinct encodings* or *succinct data structures*), most of which have been developed during my PhD.</footnote>
<figure><img src="image_50.png" /><figcaption>Figure 4.2: A few steps performed by Edgebreaker [Ros99]. The traversal starts from an initial seed (green) face and performs a depth-first visit of the dual graph (blue triangles belong to the visited region).</figcaption></figure>

<figure><img src="image_51.png" /><figcaption>Figure 4.3: Edgebreaker encoding sequence: there are five cases to consider, depending on the adjacencies of each traversed (blue) triangle. These cases are described by five symbols {C, L, E, R, S}: the most frequent case, encoded by the symbol C, is when the visited triangle is incident to a new unvisited vertex, which occurs $n-3$ times. If we use 1 bit for symbol C and 3 bits for symbols {L, E, R, S}, the resulting encoding sequence (whose length is $m-1 < 2n$) can be compressed using at most $1 \cdot (n-3) + 3 \cdot n \approx 4n$ bits. Observe that in the planar case a more sophisticated encoding of the CLERS sequence leads to a better compression rate of 3.67 bpv [KR99].</figcaption></figure>

developed since the early nineties in both the geometry processing and graph algorithms communities fits into the framework above. For instance, the popular Edgebreaker compression scheme proposed by Rossignac [Ros99] relies on an incremental growing-region approach (illustrated in Fig. 4.2). The algorithm performs an incremental traversal of the dual graph starting from an initial seed face: Edgebreaker makes use only of five symbols in order to encode a spanning tree of the dual graph and its complement, a spanning tree of the primal graph (refer to Fig. 4.3): a triangulation with $n$ vertices can be encoded using at most $4n$ bits.

### 4.1.2 Optimal encodings achieving information-theory lower bounds

**PLANAR CASE.** The Edgebreaker encoding above is both simple and quite compact, since its compression rate of 4 bpv (bits per vertex) is not far from the information-theory asymptotic lower bound given by

$$ \frac{1}{n} \log_2 |\mathcal{T}_n| = \frac{2(4n-3)!}{n(3n-1)!(n)!} \approx \log_2 (4^4/3^3) \approx 3.2451 \text{ bpv} \quad (4.1) $$

(where $|\mathcal{T}_n|$ is the number of rooted planar 3-connected triangulations with $n+2$ vertices, found by Tutte [Tut62]).

The bound above is attained by the nice bijective construction due to Poulalhon and Schaeffer [PS06], which relies on the correspondence between minimal Schnyder woods and a special class of spanning trees (having two stems per node); this bijection provides a combinatorial proof of the counting formula for $|\mathcal{T}_n|$, also yielding efficient procedures for uniform random sampling (this construction will be sketched in Section 4.3).

**HIGHER GENUS CASE.** In the higher genus case there does not exist an exact enumeration formula, nevertheless an asymptotic estimate [Ga093] of the number of genus g rooted triangulations with $n$ vertices leads to the information theory lower bound of $3.245n + \Omega(g \log n)$, i.e., the exponential growth rate is the same in every genus.

For the genus 1 case, a special class of toroidal Schnyder woods allowed Despré, Gonçalves, and Lévêque [DGL17] to generalize the Poulalhon and Schaeffer bijection, in order to obtain an optimal encoder for toroidal triangulations. Unfortunately, in the higher genus g case there are still several questions that remain open involving the existence of Schnyder woods: bijective constructions based on special spanning trees are still to be found.

## 4.2 ENCODING TRIANGULATIONS IN ARBITRARY GENUS

A main application that motivated our definition of g-Schnyder woods was to extend to higher genus the encoding procedure of [HKL99; BB07] based on Schnyder woods: while not being asymptotically optimal, this approach is quite simple and yields a linear-time encoding achieving the same bound as Edgebreaker.

The encoding based on Schnyder woods turns out to be extremely useful for dealing in practice with compact data structures: as we will illustrate in Section 4.4. A simple adaptation leads to a very efficient way of decoding a compact data structure from compressed format in a streamable way: this leads to drastically reduce the memory requirements consumed in the pre-processing constructive phase.
<figure><img src="image_52.png" /><figcaption>Figure 4.4: Encoding of a plane triangulation $\mathcal{T}$ (endowed with a Schnyder wood orientation): $\mathcal{T}$ is encoded by a pair of binary words, encoding respectively the red tree $\overline{T_0}$ and the tails of black edges (center). The information concerning blue edges is redundant and can fully be retrieved by applying the local Schnyder condition (right).</figcaption></figure>

**THE PLANAR CASE.** In the planar case, Schnyder woods yield a simple encoding procedure for triangulations, as described in [HKL99] and more recently in [BB07]. For a triangulation with $n$ vertices, $W, W'$ have length at most $2n$, hence the coding word has total length at most $4n$.

More precisely, a planar Schnyder wood with $n$ vertices is encoded by two parenthesis words $W, W'$ of respective lengths $2n-2$ and $2n-6$. Let $\overline{T_0}$ be the tree $T_0$ plus the two outer edges incident to $V_0$. Call $\theta$ the corner incident to $V_0$ in the outer face. The first word $W$ is the parenthesis word (also called Dyck word) that encodes the tree $\overline{T_0}$, that is, $W$ is obtained from a ccw walk (i.e., the walker has the infinite face on its right) around $\overline{T_0}$ starting at $\theta$, writing an opening parenthesis at the first traversal of an edge of $\overline{T_0}$ (away from the root) and a closing parenthesis at the second traversal (toward the root). The second word $W'$ is obtained from the same walk around $T_0$, but $W'$ encodes the edges that are not in $\overline{T_0}$, i.e., the edges of color 1 and 2. Precisely, during the traversal, write a '0' symbol in $W'$ each time an outgoing edge in color 1 is crossed and write a '1' symbol in $W'$ each time an ingoing edge of color 2 is crossed (this corresponds to a unary encoding of the ingoing degree of edges of color 2 at each vertex $v \in V \setminus \{V_0, V_1\}$).

The string below corresponds to the encoding of the triangulation in Fig. 4.4 (vertices are ordered according to the ccw-DFS traversal of $\overline{T_0}$):

( ) ( ) ( ) ( ) ( ( ) ( ) ) ( ) 00001101010111

For the sake of clarity, we can decorate this code by vertex indices:

(1) (2) (3) (4) (5) (6) (7) (8) (9) (02) (03) (04) (05) (106) (107) (108) (111)

In the example above the black word encodes the in-black-degrees of vertices, which are respectively 0, 0, 0, 0, 0, 2, 1, 1, 3.

While not being asymptotical optimal, this encoding has the advantage of being extremely simple to implement and fast in practice: as confirmed by the experiments reported in Fig. 4.5 our Java implementation is able to process between 2.2M and 3.7M vertices per second (which makes this approach highly competitive with prior works on mesh compression).

**Remark.** Observe that, in the planar case, because of the symmetry of the definition of Schnyder woods in the three colors, one could perform a contour traversal of the spanning tree $T_1$ (or $T_2$) instead of $T_0$, and the traversal may be in either cw or ccw direction (similar arguments would apply).

### 4.2.1 Encoding in higher genus

To encode a genus $g$ triangulation $\mathcal{T}$ of size $n$ we proceed in a similar way as in the planar case except that we endow $\mathcal{T}$ with a $g$-Schnyder wood

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

<figure><img src="image_54.png" /><figcaption>Figure 4.5: Runtime cost of the algorithm for encoding planar triangulations (it includes the pre-processing time, for computing the Schnyder wood). Timings are expressed in seconds as a function of the size (millions of vertices). In our tests we allocate 6GB of RAM memory for running our Java implementation [CD18].</figcaption></figure>
puted in O(n) time according to Theorem 3.4, and thus we have to deal with the special edges involved in Definition 3.1.

Let $\overline{T}_2$ be the spanning tree of $\mathcal{T}$ consisting of the edges in color 2 plus the two edges $\{V_0, V_2\}$ and $\{V_1, V_2\}$ (refer to Fig. 4.6). Let $G_2$ be the graph $\overline{T}_2$ plus the 2g special edges (according to Proposition 3.5 this is a cut-graph of $\mathcal{T}$). As in previous section we classically encode $G_2$ as the Dyck word $W$ for $\overline{T}_2$, augmented by 2g memory blocks, each of size $O(\log(n))$ bits, so as to locate the two extremities of each special edge: in each memory block we also store the colors and directions of the two sides of the special edge (as depicted in the middle picture of Fig. 4.6). Hence $G_2$ is encoded by a word $W$ of length $2n - 2 + O(g \log(n))$. The encoding of the g-Schnyder wood is completed by a second binary word $W'$ that is obtained from a clockwise walk along the (unique) face of $G_2$ (cw means that the face is on the right of the walker) starting at the corner $\theta$ incident to $V_2$ in the root-face. Along this walk, we write a '0' bit when crossing a non-special outgoing edge of color 0 and we write a '1' bit when crossing a non-special ingoing edge of color 1 (this corresponds to encode the ingoing degree of color 1 edges). Since there are $2n - 6 + 4g$ non-special edges of color 0 or 1, the word $W'$ has length $2n - 6 + 4g$. Therefore the pair of words $(W, W')$ is of total length $4n + O(g \log(n))$. Observe that these words can be obtained in time $O((n+g)g)$ from a g-Schnyder wood on $\mathcal{T}$, and the g-Schnyder wood itself can be computed in time $O((n+g)g)$.

The correctness of this procedure – the fact that the pair $(W, W')$ actually encodes the g-Schnyder wood (and in particular the triangulation) – relies on the two lemmas below (the proofs are omitted here and can be found in [CAFL09]). First Lemma states that the information given by non-special edges of color 0 is redundant.

**Lemma 4.1** Let $\mathcal{T}$ be a triangulation endowed with a g-Schnyder wood. Then the g-Schnyder wood can be recovered after the deletion process that consists in removing all the non-special edges of color 0.

**Lemma 4.2** Let $\mathcal{T}$ be a triangulation endowed with a g-Schnyder wood and consider the corresponding cut-graph $G_2$. Let $\theta$ be the corner incident to $V_2$ in the root-face ($\theta$ is also a corner of $G_2$). Let $e$ be a non-special edge of color 1. Then, during a cw walk along $G_2$ (i.e., with the unique face of $G_2$ on the right of the walker) starting at $\theta$, the outgoing brin of $e$ is crossed before the ingoing brin of $e$.

**DECODING.** We can now describe how to reconstruct the Schnyder wood from the two words $(W, W')$. First, construct the cut-graph $G_2$ using $W$. Note that the directions of edges and colors of the two sides of each special edge of $G_2$ are known from $W$. Hence, by the local conditions of Schnyder woods, we can already insert the outgoing brins of color 0 or 1 that are non-special (a non-special brin is a brin of a non-special edge). The non-special outgoing brins of color 0 are ordered as $b_1, b_2, \dots, b_k$ according to the order in which they are crossed during a cw walk along $G_2$ (i.e., with the unique face of $G_2$ on the right of the walker). Next, the word $W'$ indicates where to insert the non-special ingoing brins of color 1. Precisely, factor $W'$ as

$$W' = 1^{r_1} 0 1^{r_2} 0 1^{r_3} \dots 0 1^{r_{k+1}},$$

where the integers $r_i$'s are allowed to be zero. Then, for each $i \in [1..k]$, insert $r_i$ ingoing brins of color 1 in the corner $(b_i, \text{follower}(b_i))$ (where the follower of a brin $b$ is the next brin after $b$ in cw order around its origin). And insert

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

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

<figure><img src="image_57.png" /><figcaption>Figure 4.6: Encoding of a toroidal triangulation using our scheme based on g-Schnyder woods.</figcaption></figure>
$r_{k+1}$ ingoing brins of color 1 in the corner incident to $V_1$ delimited to the right by $\{V_1, V_0\}$.

Afterwards, we use Lemma 4.2 to form the non-special edges of color 1. Write a parenthesis word $\pi$ obtained from a cw walk along $G_2$ starting at $\theta$, writing an opening parenthesis each time a non-special outgoing brin of color 1 is crossed and writing a closing parenthesis each time a nonspecial ingoing brin of color 1 is crossed. Then, Lemma 4.2 ensures that the match- ings of $\pi$ correspond to the non-special edges of color 1 in the Schnyder wood, so we just have to form the non-special edges of color 1 according to the matchings of $\pi$.

Finally, since the edges of color 0 are redundant (by Lemma 4.1), there is no ambiguity to insert the edges of color 0 at the end (i.e., complete the already inserted outgoing half-edges of color 0 into edges).

To conclude, the non-special edges of color 0 are redundant, the cut-graph can be encoded by a parenthesis word $W$ of length $2n-2$ (for the tree $\overline{T_2}$) plus $O(g \log(n))$ bits of memory for the special edges, and the edges of color 1 can be inserted from a word $W'$ of length $2n-6+4g$. Clearly the reconstruction of the Schnyder wood from $(W, W')$ takes time $O((n+g)g)$, since it just consists in building the cut-graph $G_2$ and walking cw along $G_2$. All in all, we obtain the following result:

**Theorem 4.3 (Castelli Aleardi, Fusy, and Lewiner [CAFL09])** A triangulation of genus $g$ with $n$ vertices can be encoded—via a $g$-Schnyder wood—by a binary word of length at most $4n + O(g \log(n))$. Coding and decoding can be done in time $O((n+g)g)$.

**CONCLUDING REMARKS.** While not asymptotically optimal, the encoding above matches the same compression rate of the *Edgebreaker* encoder in the genus $g$ case, being very close to the optimal information theory bound. In the next section we will explain how to encode triangulations on surfaces of arbitrary genus (possibly having boundaries) matching the asymptotic optimal bound (Theorem 4.5). It is worth nothing that the solution of Theorem 4.3 is conceptually simpler to implement and faster: the encoding/decoding is done in $O((n+g)g)$ time, while the solution offered by Theorem 4.5 requires more than linear time to be computed.

Another advantage is that the encoding of Theorem 4.3 can be combined with other algorithmic tools to design a more sophisticated code that supports adjacency queries in $O(1)$ time, as done in [Chu+98; Bar+12]$^2$, or to obtain compact practical data structures admitting fast implementations (as the ones described in Section 4.4).

## 4.3 OUR CONTRIBUTION: OPTIMAL ENCODING OF TRIANGULATIONS WITH FIXED TOPOLOGY

In this section we sketch our solution$^3$ for optimally encoding a triangulation of arbitrary topology (possible having handles and boundaries). More precisely, we consider of class of triangulations with fixed topology, which are simple triangulated maps (no loops, no multiple edges) of genus $g$ possibly having $b \ge 0$ boundaries: all faces are triangles, except for $b$ marked *boundary* faces (also called *boundaries*) which are assumed to be pairwise disjoint (and without self-intersections). Such maps are rooted when there is

<footnote n="2">2 The results obtained in [Bar+12], a collaboration with J. Barbay, M. He and I.Munro, pertain to the design of succinct representations and are not included in this document.</footnote>

<footnote n="3">3 The contribution of this section originates from Castelli Aleardi, Fusy, and Lewiner [CFL10].</footnote>
a distinguished marked edge (the root) incident to a non-boundary (root) face.

Our solution relies on the combination of previous combinatorial tools with a planarizing strategy: the main idea consists in recursively cutting the surface along non contractible cycles in order to reduce its genus. Thus the problem of encoding a triangulation with fixed topology (given by the number of its boundaries and its genus) reduces to the problem of encoding a planar triangulation with boundaries, which can be solved with our extension of the Poulalhon and Schaeffer [PS06] bijection.

It is worth noting that more recently an elegant generalization of the Poulalhon and Schaeffer bijection to the genus 1 case has been proposed by Despré, Gonçalves, and Lévêque [DGL17], providing an optimal encoding for toroidal triangulations. Compared to the planar case with no boundary, our construction is not bijective but the encoding is still asymptotically optimal in the information theory sense, and allows us to deal with triangulations of arbitrary topology (bounded number of boundaries and handles): an advantage is that our strategy is rather simple and does not involve the computation of special crossing toroidal Schnyder woods as in [DGL17].

**ORIENTATIONS AND CANONICAL SPANNING TREES.** An $\alpha$-orientation of a planar map $M$ is *minimal* if there is no counter-clockwise directed cycle, and is *accessible* if from every vertex one can reach the root-vertex by an oriented path. To such an orientation $O$ is associated the so-called *canonical spanning tree* for $O$ [Bero7], which is the unique spanning tree $T$ satisfying:

1. the edges of $T$ are oriented toward the root-vertex,

2. every edge $e \in M \setminus T$ has on its right the interior of the unique cycle of $e + T$.

The canonical spanning tree can be computed in linear time (according to the number of edges) by a traversal algorithm [PS06; Bero7]. The *fully decorated spanning tree* $F$ for $O$ is obtained by cutting each edge $e \in M \setminus T$ in its middle, leaving an *outgoing stem* (incident to the origin of $e$) and an *ingoing stem* (incident to the end of $e$), see Figure 4.7(c). Property 2 ensures that $O$ can be recovered from $F$, since the edges of $M \setminus T$ correspond to the matchings of the cyclic parenthesis word formed by the stems in clockwise order around the unique face of $F$ (outgoing stems being seen as opening parentheses and ingoing stems as closing parentheses).

### 4.3.1 Encoding plane triangulations (Poulalhon and Schaeffer [PS06] bijection)

Let $\mathcal{T}$ be a plane triangulation with $n + 2$ vertices and root face $\{V_0, V_1, V_2\}$. The first step consists in computing a minimal Schnyder wood and the corresponding 3-orientation, denoted $O$, which is accessible with respect to every outer vertex. Then consider the corresponding fully decorated spanning tree, denoted $F$ (see Fig. 4.7(c)). Since all faces are of degree 3, there is no loss of information in deleting ingoing stems (because there is a unique way to place the ingoing stems in such a way that the map obtained by matching outgoing with ingoing stems is a triangulation). One can also delete the branch $(V_1, V_0)$, $(V_0, V_2)$ without loss of information. The obtained tree with only outgoing stems is called the *reduced decorated spanning tree* $R$ of $M$ (see Fig. 4.7(d)): $R$ is a rooted plane tree with 2 stems at each of the $n$ nodes (the extremity of a stem being not considered as a node). As shown in [PS06],

<figure><img src="image_58.png" /><figcaption>Figure 4.7: A planar rooted triangulation $M$ endowed with its minimal 3-orientation (a), and the corresponding spanning tree $T$, rooted at $V_2$ (b).</figcaption></figure>
<figure><img src="image_59.png" /><figcaption>Figure 4.8: Correspondence between a triangulation M with 2 boundaries (a), and a decorated plane tree with 2 boundaries, spanning all vertices of $M \setminus \{V_0, V_1\}$ (h).</figcaption></figure>

such a tree can be represented by a binary word of length $4n$ and weight $n$, which can be compressed leading to an encoding of size $\sim \log_2(\frac{4n}{n})$, matching the asymptotic bound given by (4.1).

### 4.3.2 Encoding planar triangulations with multiple boundaries

Here starts our contribution, which is to keep an optimal encoding scheme in case of boundaries. Let $M$ be a plane triangulation with $b > 0$ boundaries, $n + 2$ non boundary vertices, and $k$ boundary vertices. Assume without loss of generality that an outer (non-boundary) face $\{V_0, V_1, V_2\}$ for $M$ is fixed that does not touch any of the boundaries (if no such face exists, create it inside an arbitrary non-boundary face, this adds only 3 vertices and will have no effect on the length of the coding word asymptotically). Define the *completed triangulation* for $M$ as the planar triangulation $M^c$ obtained by adding a star in each boundary face (see Fig. 4.8(b)); $M^c$ is a triangulation with $n + k + b$ vertices and no boundary. Endow $M^c$ with Schnyder wood and consider the corresponding 3-orientation. Then contract each of the $b$ stars $S_1, \dots, S_b$ into a single so-called *special* vertex $s_1, \dots, s_b$ (each contraction deletes the edges of the star and the edges on the contour of the corresponding boundary face). The orientation inherited by the 3-orientation of $M^c$ is such that every non special vertex has outdegree 3, while every special vertex $s_i$ has outdegree $k_i + 3$, with $k_i$ the size of the corresponding boundary. The contracted orientation is still accessible with respect to vertices $\{V_0, V_1, V_2\}$, but it may not be minimal, even if coming from the minimal 3-orientation of $M^c$; indeed a path connecting two vertices on the same boundary might become a ccw circuit after contraction (as shown in Fig. 4.8(d)). However a procedure discussed in [BWoo] allows us to make —in linear time— the contracted orientation minimal (by successively reversing ccw circuits) while keeping the same outdegree at each vertex. Moreover the obtained minimal orientation is still accessible, because returning circuits does not affect accessibility. So we can now consider the fully decorated spanning tree for the orientation, see Fig. 4.8(f). Then we uncontract each special vertex back into the original boundary face and obtain a fully decorated plane tree with boundaries. Without loss of information we can delete ingoing stems and the branch $(V_0, V_1)$, $(V_0, V_2)$, to obtain the
so-called reduced decorated plane tree with boundaries R for M. The tree R belongs to the family $P_{n,k}^{(b)}$ of plane trees with b boundaries, n non-boundary vertices, k boundary vertices, and decorated with stems as follows: 1) each non-boundary vertex carries two stems, 2) for 1, ..., b, the i-th boundary, of size called $k_i$, carries overall $k_i + 2$ stems 4. We obtain:

**Lemma 4.4 ([CFL10])** For fixed $b > 0$, any tree in $P_{n,k}^{(b)}$ can be encoded in a number $\ell(n, k)$ of bits that satisfies

$$ \ell(n, k) \sim 2k + \log_2 \binom{4n + 2k}{n} \quad \text{as } n + k \to \infty. $$

The encoding of the tree is done by a contour word similarly as in [PS06]. Moreover, this encoding is asymptotically optimal with respect to n and k (when $n + k \to \infty$), since it matches the lower bound that one can derive from Brown's counting formula [Bro64].

### 4.3.3 Encoding in higher genus

For dealing with the higher genus case, it suffices to make some simple observations. First, as discussed in [McDo8] (Lemma 4.1), for any graph G on a surface S of genus $g > 0$ with n vertices, there exists a non-contractible cycle C on S such that C crosses G at vertices only, and $|G \cap C| \le \sqrt{2n}$; C is in fact the cycle with smallest number of intersections and can be computed in time $O(n \log(n))$ for fixed genus g [Kuto6]. For a triangulation M on S with b boundaries (boundaries seen as faces), C can be deformed in each triangular face f to pass by one edge around f (but we do not deform C inside the boundary faces). After this, cut S along C; this yields a triangulation $M'$ of genus $g-1$ with two special boundary-faces $f_1, f_2$ bounded each by C (indeed, cutting splits C into two copies), with otherwise at most $2b$ boundaries (because each of the b boundaries of M might be crossed by C, thus becoming two boundaries after cutting). We add a star into $f_1$ and $f_2$, so the boundaries are only the ones arising from the boundaries of M (the locations of the two special stars have be stored to recover M from $M'$, which costs only $O(\log(n))$ in memory). If M has n non-boundary vertices and k boundary vertices, $M'$ will have $n' \le n+2+|C|$ non-boundary vertices and $k' \le k+2b+|C|$ boundary vertices, with $|C| \le \sqrt{2(n+k)}$. By induction on g, $M'$ can be encoded asymptotically optimally, i.e., with a word of length $\ell(n', k') \sim 2k' + \log_2 \binom{4n'+2k'}{n'}$. Since $\ell(n', k') \sim \ell(n, k)$ when $n+k \to \infty$ and when $n'+k' = n+k+O(\sqrt{n+k})$, and since only memory $O(\log(n))$ is necessary to recover M from $M'$, the encoding in genus g is also asymptotically optimal.

**Theorem 4.5 (Castelli Aleardi, Fusy, and Lewiner [CFL10])** Given an orientable surface S of fixed topology $\tau = (g, b)$, it is possible to encode any triangulation on S having n inner vertices and k boundary vertices, such that the length $\ell(n, k)$ of the encoding word satisfies, as $n+k \to \infty$:

$$ \ell(n, k) \sim \log_2 |\mathcal{T}_{n,k}| $$

where $\mathcal{T}_{n,k}^{(\tau)}$ denotes the set of triangulations on S with n inner vertices and k boundary vertices. Moreover, the encoding phase requires $O(n+k)$ time if $g=0$ and $O((n+k)\log(n+k))$ time if $g > 0$, while decoding takes $O(n+k)$ time.

<footnote n="4">4 R satisfies this property since, in the contracted tree, the total outdegree $k_i + 3$ of the special vertex $s_i$ consists of one outgoing edge to the father of $s_i$ plus $k_i + 2$ outgoing stems</footnote>
<table><caption>Table 2: Comparison between existing data structures for triangle meshes. All storage and runtime bounds hold in the worst case. The degree of the accessed vertex is denoted d. Storage costs are expressed in terms the number of references (as a function of the number n of vertices).</caption><thead><tr><th>Data structure</th><th>size<br>(references)</th><th>navigation</th><th>vertex<br>access</th><th>vertex<br>adjacency</th><th>dynamic<br>updates</th></tr></thead><tbody><tr><td>Edge-based data structures [GS85; Bau72; Bau75]</td><td>18n + n</td><td>O(1)</td><td>O(1)</td><td>O(d)</td><td>yes</td></tr><tr><td>triangle based [Boi+02]/Corner Table</td><td>12n + n</td><td>O(1)</td><td>O(1)</td><td>O(d)</td><td>yes</td></tr><tr><td>Directed edge [CKS98]</td><td>12n + n</td><td>O(1)</td><td>O(1)</td><td>O(d)</td><td>yes</td></tr><tr><td>Compact half-edge [AJ05]</td><td>12n + n</td><td>O(1)</td><td>O(1)</td><td>O(d)</td><td>yes</td></tr><tr><td>2D catalogs [CDM11]</td><td>7.67n</td><td>O(1)</td><td>O(1)</td><td>O(d)</td><td>yes</td></tr><tr><td>Star vertices [KT01]</td><td>7n</td><td>O(d)</td><td>O(1)</td><td>O(d)</td><td>no</td></tr><tr><td>TRIPOD [SS99] or our Thm 4.7</td><td>6n</td><td>O(1)</td><td>O(d)</td><td>O(d)</td><td>no</td></tr><tr><td>SOT [GR09]</td><td>6n</td><td>O(1)</td><td>O(d)</td><td>O(d)</td><td>no</td></tr><tr><td>ESQ [CADR12]</td><td>4.8n</td><td>O(1)</td><td>O(d)</td><td>O(d)</td><td>yes</td></tr><tr><td>Thm 4.8 (no vertex reordering)</td><td>5n</td><td>O(1)</td><td>O(d)</td><td>O(d)</td><td>no</td></tr><tr><td>Thm 4.8 (with vertex reordering)</td><td>4n</td><td>O(1)</td><td>O(d)</td><td>O(d)</td><td>no</td></tr><tr><td>Thm 4.9 (with vertex reordering)</td><td>5n</td><td>O(1)</td><td>O(1)</td><td>O(1)</td><td>no</td></tr></tbody></table>

## 4.4 COMPACT MESH DATA STRUCTURES: RELATED WORKS

A basic requirement for mesh data structures, in addition to representing the combinatorics and geometry of a 3D shape, is the *traversability*: the user should be provided with fast navigational operators allowing to perform a mesh traversal (such as walking around a vertex, or performing a DFS visit of the primal or dual graph). Sometimes the user may ask for additional functionalities such as the *indexability* (allowing to access in constant to each vertex or triangle given its index) or the *modifiability* (the manipulation of meshes may require to perform updates such as vertex insertions/deletions, edge collapses and edge flips). The existing representations which are commonly used in practice are easy to implement and provides fast navigational operators and dynamic local updates. But they have a drawback: in order to match these performances they store a lot of information, which makes the data structures quite redundant and not really suitable for representing very large meshes (Table 2 reports comparisons of mesh representations).

**PRACTICAL SOLUTIONS.** An effective way of for dealing with huge meshes is to design *compact data structures* requiring small storage while still guaranteeing a fast and practical way of accessing mesh elements.

Succinct representations [CDS05a; CDS05b; CDS08], run under the *word-RAM model*, provide an optimal solution but are mainly of theoretical interest, since the amount of memory required in practice is quite important even for very large meshes. Some attempts to exploit the algorithmic framework of succinct representations in practice had lead to a space efficient dynamic data structure [CDM11]. The main idea is to gather together neighboring faces into small groups of triangles (called *patches*). While references are still of size $Θ(\log n)$, grouping triangles allows us to save some references (corresponding to edges internal to a given patch). In particular a triangulation (possibly having handles and boundaries), can be represented using at most 7.67 references per vertex, while supporting $O(1)$ time navigation and local updates in $O(1)$ amortized time [CDM11] (a more concise solution [CADR12] requiring 4.8n references/vertex can be obtained through face/vertex reordering, slightly increasing the cost for updates).

Compact data structures aim to reduce the connectivity cost, since connectivity largely exceeds the geometry cost. The typical cost of geometric coordinates ranges from $3 \times 16 = 48$ to $3 \times 32 = 96$ bits per vertex (bpv). While storing connectivity requires between $13 \times 32 = 416$ bpv and $19 \times 64 = 1216$ bpv (depending whether triangle, vertex indices are described with 32 or 64 bits per reference) adopting standard data structures [Bau75; Boi+02], as reported in Table 2.
<figure><img src="image_60.png" /></figure>

<figure><img src="image_61.png" /><figcaption>Figure 4.9: Illustration of the SOT data structure [GR09].</figcaption></figure>

<figure><img src="image_62.png" /><figcaption>Figure 4.10: We have implemented the construction of the LR data structure [Gur+11a] and evaluated its compression performances: results are expressed in terms of references per vertex. Meshes are sorted from left to right according to $d_6$, the proportion of degree 6 vertices (regular meshes are listed leftmost). Our tests involve real-world meshes from the aim@shape repository and confirm the intuition that LR achieves good compression rates for regular meshes (with high value of $d_6$).</figcaption></figure>

### REDUCING REDUNDANCY THROUGH FACE REORDERING.
One of the ingredients for reducing the storage requirements is to perform a reordering of the faces or the edges of the input mesh. The main idea used in the SOT data structure [GR09], illustrated in Fig. 4.9, is to implicitly represent the map from triangles to corners (triangle operator), and the map from corners to vertices (vertex operator), through a face reordering. First match each vertex to an incident triangle (in such a way a triangle is matched with at most one vertex). Then permute triangles in such a way that the triangle associate with the i-th vertex $v_i$ has number i (thus the first n triangles appearing in this ordering are the ones associated with a vertex). The corners of a triangle are listed consecutively, and the first one corresponds to the vertex matched for the triangle. The incidence relations are stored in an array O (of size 3m) having 3 entries per triangle: $O[i]$ stores the index of the corner opposite to $c_i$ (which is matched to vertex $v_i$, for $i \le m$). Corners operators are easily supported in O(1) time performing arithmetic operations. The only operation that cannot be performed in constant time is vertex access: retrieving vertex $v_i$ requires to walk around its incident faces until $c_i$ is reached ($v_i$ being matched to $c_i$).

**Theorem 4.6 (Gurung and Rossignac [GR09])** *Given a triangulation (possibly having handles and boundaries), there exists a data structure using 6 rpv which supports O(1) time navigation (retrieving a vertex of degree d requires O(d) time).*

### MORE CONCISE HEURISTIC SOLUTIONS.
Adopting some interesting heuristics one may obtain even more compact solutions [Gur+11b; Gur+11a; Gur+13], requiring better space requirements in practice, but with no theoretical guarantees in the worst case. For instance, the face pairing approach of the SQUAD data structure improves the SOT bounds to about $(4 + \varepsilon)$ references per vertex: as shown by experiments $\varepsilon$ is usually a small value (between 0.09 and 0.3 for the tested meshes). Another heuristic combines the face and vertex re-ordering with computation of a nearly Hamiltonian ring spanning almost all vertices: as reported in [Gur+11a], the LR data structure is able to represent a triangulation using between 2.04 and 3.16 references per vertex in the case of regular meshes (we plot in Fig. 4.10 the experimental evaluation obtained with our implementation of the construction phase of the LR data structure).

## 4.5 OUR CONTRIBUTION: COMPACT DATA STRUCTURES FOR TRIANGULATIONS

### NAVIGATIONAL INTERFACE.
In order to design our compact data structures we have first to choose the right set operations that our solution will support. For our purposes we adopt the interface of the *winged-edge representation* [Bau72; CKS98], which offers navigational operators which are equivalent to the ones supported by the Half-edge representation. More precisely, given an edge $e = (u, v)$ oriented toward $v$, which is incident to $(u, v, w)$ (its left triangle) and to $(v, u, z)$ (its right triangle), the operators defined in Fig. 4.11 allows us to retrieve the four undirected edges $\{v, z\}$, $\{v, w\}$, $\{u, z\}$ and $\{v, w\}$, and perform full navigation in the mesh as required in geometric processing algorithms. For instance, their combination allows us to walk around the edges incident to a given face, or to iterate on the edges incident to a given vertex (as depicted in Figure 4.11).
<figure><img src="image_63.png" /></figure>

Edge(u) returns an edge outgoing from u

$$ \text{LeftBack}(e) = \{u, w\} $$

$$ \text{LeftFront}(e) = \{v, w\} $$

$$ \text{RightBack}(e) = \{u, z\} $$

$$ \text{RightFront}(e) = \{v, z\} $$

$$ \text{Source}(e) = u $$

$$ \text{Target}(e) = v $$

$$ \text{Point}(u) = (u_x, u_y, u_z) $$

```c
Degree(u) {
    // Enumerating edges incident to u
    e = Edge(u);
    f = e; d = 0;
    do {
        if (u == Source(f))
            f = LeftBack(f);
        else
            f = RightFront(f);
        d = d + 1;
    } while f != e;
    return d;
}
```

Figure 4.11: (left) Navigational operators supported by the *winged-edge representation* [Bau72]: these operators can be combined to perform mesh traversal, for example for enumerating the edges incident to a vertex (see pseudo-code on the right).

### OVERVIEW OF OUR SOLUTION.
In order to design new compact array-based data structures, we make use of two ingredients. The first idea is to exploit, as done in [SS99], the existence Schnyder woods which will allow storing only two references per edge (namely the LeftFront and RightFront incident edges). The second idea consists in performing, as done in [CKS98; GR09; Gur+11b], a reordering of cells (the edges in our case) to implicitly represent the map from vertices to edges, and the map from edges to vertices. More precisely, let us consider an input plane triangulation $\mathcal{S}$ endowed with a Schnyder wood $(T_0, T_1, T_2)$, and define the tree $\bar{T}_0$ by adding edges $(V_1, V_0)$ and $(V_2, V_0)$ to $T_0$; after adding the edge $(V_2, V_1)$ to the tree $T_1$ each edge gets a color and an orientation, as depicted in Figure 4.13.

Since the local Schnyder condition ensures exactly one outgoing edge of each color (except for vertices $V_0, V_1, V_2$) an edge $(u, v)$ can also be identified by its origin $u$ and its color $c$. For each color $c$ and each vertex $u$, we store two vertex indices $S_c^{\text{left}}[u]$ and $S_c^{\text{right}}[u]$ and two booleans $C_c^{\text{left}}[u]$ and $C_c^{\text{right}}[u]$ describing the source and color of the two neighboring edges of edge $u_c'$ as detailed below and one boolean $I_c[u]$ indicating the existence of incoming edge at $u$ of color $c$.

Vertices will be identified by integers $0 \le i < n$; and an oriented edge $(u, v)$ having source $u$ and color $c$ will be represented by the pair $(u, c)$ (also denoted $u_c'$).

#### 4.5.1 Our first solution: scheme description

Combining Schnyder woods and the re-ordering of edges one can obtain an array-based representation using only 6 references: this first representation is still quite simple (and relatively easy to implement), so that we can shortly provide its complete description and sketch the main arguments underlying its correctness.

Our data structure consists of several arrays of size $n$:

- three arrays of booleans $I_{\text{red}}$, $I_{\text{blue}}$, and $I_{\text{black}}$ (I standing for *incoming*),

- six arrays of booleans $C_{\text{red}}^{\text{left}}$, $C_{\text{red}}^{\text{right}}$, $C_{\text{blue}}^{\text{left}}$, $C_{\text{blue}}^{\text{right}}$, $C_{\text{black}}^{\text{left}}$, $C_{\text{black}}^{\text{right}}$ (C standing for *color*),

- six arrays of vertex indices $S_{\text{red}}^{\text{left}}$, $S_{\text{red}}^{\text{right}}$, $S_{\text{blue}}^{\text{left}}$, $S_{\text{blue}}^{\text{right}}$, $S_{\text{black}}^{\text{left}}$, $S_{\text{black}}^{\text{right}}$ (S standing for *source*),

- an array $P$ storing the geometric coordinates of the points.

In order to help the intuition we prefer to replace the three indices $\{0, 1, 2\}$ (operations are done modulo 3) with three labels $\{\text{red}, \text{blue}, \text{black}\}$ which are cyclically ordered using the operator next (and prev) defined as:
$$ \text{next}(\text{red}) = \text{blue}, $$
$$ \text{next}(\text{blue}) = \text{black}, $$
$$ \text{next}(\text{black}) = \text{red}. $$
<figure><img src="image_64.png" /><figcaption>Figure 4.13: Illustration of the data structure described by Theorem 4.7. For each vertex we store 6 references in table S, corresponding to the source of the front neighbors of the 3 outgoing edges. Tables I, C, S are drawn as an array of size n where booleans are represented by colors (green=true, pink=false).</figcaption></figure>

<figure><img src="image_65.png" /><figcaption>Figure 4.12: In the example above vertex 8 has no red incoming edges thus $I_{\text{red}}[8]$ is false (pink); the left front edge of the red edge outgoing from Vertex 8: $8_{\text{red}} = (8,5)$ is $(9,5) = 9_{\text{red}}$ thus the first box of line 8 of the array is green (same color) and contains 9.</figcaption></figure>

These arrays store the following information (refer to Figure 4.13) for a vertex u and a color c (the three vertices of the outer face do not have all their outgoing edges and must obey special rules):

$$I_c[u] = \begin{cases} true & \text{if vertex } u \text{ has at least one incoming edge of color } c \\ false & \text{otherwise} \end{cases}$$

$$S_c^{\text{left}}[u] = \text{Source}(\text{LeftFront}(u_c'))$$

$$S_c^{\text{right}}[u] = \text{Source}(\text{RightFront}(u_c'))$$

Using the coloring rules, these two neighboring edges have only two possible colors: c and next(c) (resp. prev(c)) for a left neighbor (resp. right neighbor). Arrays $C_c$ store that information (see Fig. 4.12 for an illustration):

$$C_c^{\text{left}}[u] = \begin{cases} true & \text{if } \text{Color}(\text{LeftFront}(u_c')) = c \\ false & \text{otherwise} \end{cases}$$

$$C_c^{\text{right}}[u] = \begin{cases} true & \text{if } \text{Color}(\text{RightFront}(u_c')) = c \\ false & \text{otherwise} \end{cases}$$

**Theorem 4.7 (Castelli Aleardi and Devillers [CD18])** Let $\mathcal{T}$ be a plane triangulation with n vertices. The representation described above requires 6n references, while allowing support of Target operator in O(d) time (when dealing with a degree d vertex) and all other operators in O(1) worst case time.

**PROOF:** Let e be an edge of color c, with source u and target v, whose incident left and right triangles are (u,v,w) and (v,u,z) respectively. The navigational operations supported by the Winged-edge data structure can be implemented as described below.

**OPERATORS Edge(u) AND Point(u):** to get the index of an edge incident to a given vertex u we simply returns the edge $u_{\text{red}}$. The geometric coordinates of vertex u are naturally stored in $P[u]$.
**OPERATOR Source(e):** is a trivial operation since $e = (u, v)$ is encoded as the pair $(u, c)$ in our representation.

**OPERATOR LeftFront(e):** by definition of arrays S and C, LeftFront(e) is the edge of source $S_{Color(e)}^{left}$[Source(e)] and color Source(e) if the boolean value $C_{Color(e)}^{left}$[Source(e)] is true, and color next(Color(e)) otherwise.

**OPERATOR LeftBack(e):** We have to distinguish three cases, depending on the color of edges $(u, w)$ and $(v, w)$ (as illustrated in Figure 4.14):

**Case 1:** $I_{prev(Color(e))}$[Source(e)] is false. This case is easy to handle, since $(u, w)$ is the edge with source $u$ and color next(Color(e)) (see Fig. 4.14(c)), there is no incoming blue edge at $u$: LeftBack(e) must be red and outgoing at $u$).

**Case 2:** $I_{prev(Color(e))}$[Source(e)] is true and $C_{Color(e)}^{left}$[Source(e)] is true. Then $(w, v)$ is of color Color(e) and $(v, w)$ can be accessed as LeftFront(e) and LeftBack(e) is the edge with source Source(LeftFront(e)) and color prev(Color(e)) (there are incoming blue edge at $u$, thus LeftBack(e) is blue). Since LeftFront(e) = {$v, w$} is black, it is oriented from $w$ to $v$ and its source is also the searched source of LeftBack(e)).

**Case 3:** $I_{prev(Color(e))}$[Source(e)] is true and $C_{Color(e)}^{left}$[Source(e)] is false, then $(v, w)$ is of color next(Color(e)) and LeftBack(e) is the edge given by LeftFront(LeftFront(e)). As in Case 2 LeftBack(e) is blue, but the edge LeftFront(e) = {$v, w$} is red and oriented from $v$ to $w$. LeftBack(e) is then accessible as LeftFront(LeftFront(e)).

**OPERATOR Target(e):** unfortunately we have not stored enough information to return $v$ in $O(1)$ time: the idea is to iteratively turn around vertex $v$ (running, for example, the code given in Fig. 4.11), starting from edge $(u, v)$ in cw direction (or ccw direction) until we get an edge $e' = (v, x)$ having $v$ as source. Then compute Source($e'$) in $O(1)$ time as above, which results in the target of $(u, v)$. This procedures ends after at most $d-3$ steps (for a vertex $v$ of degree $d$), since each vertex has 3 outgoing edges.

**OPERATORS RightBack(e) AND RightFront(e):** observe that the traversal of the right face $(u, v, z)$ incident to $(u, v)$ can be handled in a similar manner as above. Operators RightBack(e) and RightFront(e) can be deduced by symmetry from operators LeftBack(e) and LeftFront(e), because of the symmetry of Schnyder woods and of our use of reference. □

<figure><img src="image_66.png" /><figcaption>Figure 4.14: Case analysis of Theorem 4.7: in these pictures the edge $(u, v)$ is assumed to be black.</figcaption></figure>

### 4.5.2 Further reducing the space requirements

In order to save one (or two) references per vertex, we make use of maximal Schnyder woods and we allow to permute input vertices (reordering the vertices according to a given permutation). One main ingredient is to make use of a breadth-first search traversal of $\overline{T}_0$, whose corresponding vertex ordering (denoted cwBFS) has the following useful property: the vertices having the same parent vertex $u$ in $\overline{T}_0$ will have consecutive labels, when traversed turning cw around $u$ from $u_{black}$ (see Figure 4.15). We then re-order all vertices (their associated data) according to their cwBFS label, and we store entries in table C accordingly. This allows us to save one reference per vertex: we do not store a reference to RightFront for edges in $\overline{T}_0$, which
<figure><img src="image_67.png" /><figcaption>Figure 4.15: A planar triangulation (endowed with its maximal Schnyder wood) whose vertices are labeled according to the cwBFS traversal of tree $\overline{T_0}$ (top). Bottom pictures illustrate two cases involved in the proof of Theorem 4.8: we now store only one reference for red edges, since most adjacency relations between edges in $\overline{T_0}$ are implicitly described by the cwBFS labels.</figcaption></figure>

leads us to not store tables $C_{red}^{right}$ and $S_{red}^{right}$. We retrieve the corresponding information using the ordering of vertices as explained below (it is even possible to save one more reference, but this implies to change the information involving black edges: the details are omitted here, please refer to [CD18]).

**Theorem 4.8 (Castelli Aleardi and Devillers [CD18])** Let $\mathcal{T}$ be a plane triangulation with $n$ vertices endowed with its maximal Schnyder wood. Then $\mathcal{T}$ can be represented using $5n$ references, while supporting navigation as in Theorem 4.7. If one is allowed permuting the input vertices (their associated geometric data) then $\mathcal{T}$ can be represented using $4n$ references, with the same runtime complexity.

The proof of the result above is based on a case analysis which is much more involved than the one of Theorem 4.8 and tedious to follow (omitted here). Two interesting cases are illustrated by the pictures in Figure 4.15. Compared to the representation of Theorem 4.7 we lose the information concerning RightFront for red edges (which was previously explicitly stored in $C_{red}^{right}$ and $S_{red}^{right}$): an important remark is that, given a red edge $e = (u, v)$, we can still retrieve its right siblings in $\overline{T_0}$ just using its cwBFS label. If $(z, v)$ is oriented toward $v$ (thus red as $(u, v)$), its source is simply $z = u - 1$. Otherwise, we exploit the assumption that the Schnyder wood is maximal: since clockwise oriented triangles are forbidden, the edge $\{z, u\} = \text{RightFront}(u_{red}^{\perp})$ must be black, and in this case we can retrieve it with a memory access, first computing the edge $(u, z)$, which is also black and oriented toward $z$.

### 4.5.3 Additional features

**ALL OPERATIONS IN $O(1)$ WORST CASE TIME.** We can further exploit the redundancy in our representation in order to improve the computational cost of the navigation: all navigational operations, including checking the adjacency between neighboring vertices, can be supported in worst case constant time slightly increasing the space requirements as stated below (the details are omitted here and can be found in [CD18]):

**Theorem 4.9 ([CD18])** If one is allowed permuting input points, then there exists a compact representation requiring $5n$ references which supports all navigation operators (including Target and Adjacent) in worst case $O(1)$ time.

**DECODING THE TRIANGULATION FROM COMPRESSED FORMAT.** A main issue common to many compact data structures [CADR12; CDM11; Gur+11b; GR09; Gur+11a], is that an explicit representation of the entire mesh must be kept in main memory during the whole construction phase: this is needed, for example, to process vertices and edges (or faces), which must be renumbered according to a prescribed mesh traversal. This preliminary construction phase can greatly increase the overall memory requirements, especially for very huge meshes: in addition to the space storage of the compact data structure to construct (between $4n$ and $8n$ references for most compact representations), one has to use between $19n$ references for an explicit representation (such as Winged-edge or Half-edge), and a few additional memory references for the implementation of the mesh processing (typically, a graph traversal). To address this issue, we can take advantage of the compressed format for triangle meshes described in Section 4.2, which makes use of Schnyder woods in order to reduce the storage requirements.
More precisely, it turns out that it is possible to save our array-based
compact representations in a compressed format so that we can reconstruct
on the fly our structure in linear time, without any extra memory cost and
in a streamable fashion.

The first construction of our representation still needs an explicit repre-
sentation, in particular for the computation of the Schnyder wood.

As shown in [CD18] the decoding procedure is in two steps and consists
in performing a linear scan of the two words W, W' encoding respectively
the red tree T₀ and the incoming black degree of the vertices.

In a first pass, the linear scan of the W word allows the construction of
the red tree by inserting the vertices (numbered according to the ccw-depth-
traversal) into a stack: in this way we fill all red columns of array C and S. In
parallel, we can read the word W' which allows us to fill the black columns
of array C and S. No extra memory is required for an explicit storage of the
red stack: as the blue columns are not involved during this first step, one
blue column can be used to provide an array-based implementation of such
a stack. When considering the red and black trees together, one obtains a
planar map where only blue edges are missing.

A second pass is required for retrieving the information about blue edges.
In the case where one is provided with a complete representation of such a
map (as in [HKL99; BB09]) retrieving the location of blue edges is straightforward: the source vertex of a blue edge is known by applying the local Schnyder rule (the coloring and orientation of edges around a vertex), and edge destinations can be recovered by performing a facial walk of each red/black face. In our case such this solution cannot be applied: after the first decoding step the red and black trees are recovered, but only a partial knowledge of the red/black map is available.

So we have to apply a new strategy, slightly different from the one used in
Section 4.2, which consists in iteratively discovering and visiting in cw order
the blue edges incident to a given vertex x (this procedure is performed
independently for each vertex).

The strategy for retrieving blue edges is
not trivial and requires some technical
details which are omitted here
(see [CD18] for a more detailed
explanation).

STREAMABLE ENCODING SCHEME. As described above, the first decoding phase (construction of red and black trees), requires a parallel reading of the two black and red words, or to perform a linear scan of the whole encoding in two passes: to first construct the red tree, and then to recover black edges (with a second linear scan). In practice, this can be a limitation in the case of streaming applications. In order to avoid this problem, and to make our data structure fully streamable, we can slightly modify our encoding scheme, by interleaving the symbols in the red and black words.

More precisely, the bits in the red and black words can be mixed in a sin-
gle binary word as follows. We start with the encoding of the red tree, where
( and ) symbols are replaced by 0 and 1 bits respectively. Let us assume we
are visiting and encoding a vertex v: just after the 0_v bit corresponding to
the first visit of v, we encode the black in-degree of v by writing a block
consisting of d 1 bits followed by a 0 bit. The mixed code corresponding to
the example of Figure 4.4 is given below

0 0 0 0 1 0 1 1 0 2 0 2 1 2 0 3 0 3 1 3 0 4 0 4 1 4 0 5 0 5 0 6 1 10 6 0 7 1 07 1 7 0 8 1 08 1 8 1 6 1 5 0 9 1 11 0 9 1 9 1 0.

where we provide colors and subscripts just to help intuition. As detailed
in [CD18], it is possible to distinguish between red and black symbols, since
during the decoding phase we perform a linear scan of this mixed word, by
taking into account the Schnyder local rule.
Building *Half-edge DS* from OFF

<figure><img src="image_68.png" /><figcaption>Decoding compressed format</figcaption></figure>

<figure><img src="image_69.png" /><figcaption>Figure 4.16: Comparison of the pre-processing runtime costs. The top chart reports the timing cost for building the half-edge data structure from a binary OFF file: we allocate 6GB of RAM memory for running the whole phase. The bottom chart corresponds to the whole decoding phase of our *CDS6n* data structure from the binary compressed format described in Section 4.2: in this case we only allocate 800MB of RAM for the JVM. Timings are expressed in seconds as a function of the size of the input mesh (millions of vertices) and represent the average time over several runs of our tests. All results are taken from [CD18].</figcaption></figure>

## 4.6 EXPERIMENTAL RESULTS

### 4.6.1 Preprocessing: construction vs. decoding.

We first evaluate the runtimes of our data structures concerning the pre-processing construction phase. The charts in Fig. 4.16 show the construction costs (expressed in seconds) of our data structure using 6n references (referred to as *CDS6n*, Thm 4.7) compared to the pre-processing phase involving the Half-edge data structure. The reported runtimes confirm the asymptotic linear time behaviour of all steps of our algorithms.

**CONSTRUCTING COMPACT DATA STRUCTURES FROM OFF FORMAT.** The runtimes reported in the top chart of Fig. 4.16 correspond to the construction phase of the Half-edge data structure from an input binary OFF file, storing both the geometry (3D vertex locations) and the mesh connectivity (the mesh is stored with a so-called *shared vertex representation*, where each face is represented with the indices of the three incident vertices).

Once we have in main memory the half-edge representation of the input mesh we can run the incremental algorithm to endow the triangulation with a Schnyder wood orientation and build arrays underlying our compact data structures. The overall timing cost is dominated by the construction of the Half-edge representation in main memory: this is the unique bottleneck, in terms of memory requirements, of our pre-processing phase (in order to run this phase on the tested meshes we have to allocate up to 6GB of RAM memory). It is worth noting that most compact data structures [GR09; Gur+11b; Gur+11a; Gur+13; CADR12] have the same limitation.

**MORE EFFICIENT CONSTRUCTION: DECODING THE COMPRESSED FORMAT.** One main advantage of our encoding/decoding algorithm sketched in Section 4.5.3 is that the input mesh can be directly constructed from a compressed input file, without using additional memory for an intermediate representation (such as the Half-edge data structure) and without computing the Schnyder wood, which leads in overall to a smaller construction cost. The bottom chart of Fig. 4.16 reports the runtimes of the decoding from the compressed format described in Section 4.2 (the cost includes the scan of the input file also storing the geometry information): our procedure<fnref n="5" /> is extremely fast and can be performed using small memory resources even for large meshes (only 800MB of RAM for the JVM are sufficient for the tested meshes).

### 4.6.2 Mesh navigation: runtime performances

In order to evaluate the performance of our representations, we have implemented a Java array-based version of the *Winged-edge data structure* (requiring 19 references per vertex): the plots in Fig. 4.17 report comparisons with our compact data representations.

As in previous works [CKS98; GR09; Gur+11b; Gur+11a; Gur+13; CADR12] we consider two usual processing procedures: computing *vertex degrees* (involving edge navigation) and *vertex normals* (involving vertex access operators and geometric calculations). In all tests we allocate enough memory so that all representations of the tested 3d models fit in main memory; vertices are accessed sequentially according to their original order in the input

<footnote n="5">⁵ A more detailed discussion of the implementation and performances can be found in [CD18].</footnote>
<figure><img src="image_70.png" /><figcaption>Figure 4.17: Comparison of runtime performances for the computation of vertex degrees and vertex normals. Our compact data structures are compared to our implementation of the *Winged-edge* data structure. All results are expressed in nanoseconds per vertex and represent the average over hundred of executions.</figcaption></figure>

mesh (except for the data structure using 4n references of Thm 4.8, where vertices are re-ordered according to the cw-BFS traversal of the tree $T_0$). We have written implementations of our data structure described in Thm 4.7 (referred to as *CDS6n*) and of the more compact versions described in Thm 4.8 (called *CDS5n* and *CDS4n* respectively).

**PRACTICAL INTEREST OF COMPACT DATA STRUCTURES.** As one could expect, non-compact mesh representations (e.g. *Winged-edge* data structure) are faster in general: refer to the runtimes plotted in Fig. 4.17. In overall, our data structures achieve good trade-offs between space usage and runtimes. While being between 3.17 and up to 4.75 times more compact for connectivity than *Winged-edge*, our structures are slightly slower: they lose in average on the tested meshes a factor 1.33 for *CDS6n*, 2.65 for *CDS5n* and 2.31 for *CDS4n*, when performing vertex degree computations.

Our representations are still competitive when considering the target operator, which requires O(d) time in the worst case for a vertex of degree d for our compact data structures (observe that the target operator requires O(1) time in the case of *Winged-edge*). The results reported in the right chart of Figure 4.17 provide a comparison of the runtimes for the vertex normal computation, and show that our representations are slower than other data structures by a factor between 1.5 and 2.5 in average (all geometric calculations involve simple float precision). The higher cost of the target operator for the *CDS6n*, *CDS5n* and *CDS4n* representations is compensated by the cost of geometric calculations, which dominates the runtimes, and is the same for all representations.

The implementation details are omitted here: a more comprehensive discussion on the encoding of service bits and the use of bit shifts and masks for manipulating integer references can be found in [CD18].
<figure><img src="image_71.png" /></figure>
Most graphs we encounter in computer science, discrete mathematics and
real-life applications are not random but exhibit some strong structural
properties and regularities. The main goal of graph drawing algorithms is to
compute a layout which is easily readable and helps the user to recover the
structure of the underlying graph. This problem is very challenging, one of
the main reasons being that real-world graphs are really big and difficult to
inspect: thus we need deep mathematical tools to provide guarantees on the
quality of the result and efficient algorithmic tools to obtain fast practical
implementations.

Most works tend to take profit of some assumptions on the input graph: for example the graph class to which it belongs or some properties, such as some notion of connectedness or some structural parameter. In particular graph planarity have played a crucial role in the domain of Graph Drawing since its early years, and led to the discover of beautiful mathematical theorems and deep algorithmic tools, whose interest and relevance went well beyond the original visualization purposes.

While there is a large literature on planar drawings, the problem of drawing graphs on surfaces has been addressed less frequently from both the theoretical and algorithmic point of view. This chapter focuses on my contributions<fnref n="1" /> to the problem of efficiently drawing graphs on surfaces, and provides a short overview of the main recent advances in this domain.

5.1 GRAPH DRAWING IN THE PLANE ("AS I HAVE KNOWN IT")

When dealing with planar (or locally planar) graphs a very basic problem addressed by the Graph Drawing community consists in mapping the vertices and edges of a graph onto a region in the plane or a portion of a 3D surface. Most of the time edges are represented as smooth curves (very often as straight-line segments), and the drawing is required to be *crossing-free*. Sometimes the drawing is asked to satisfy some further aesthetic criteria, in order to obtain a pleasing and readable result. For example, one could seek for *good vertex resolution* for ensuring that vertices are not too close to one another.

**FORCE-DIRECTED METHODS.** In the planar case, an elegant solution to the graph drawing problem is provided by the so-called *barycentric embedding*, one of Tutte's masterpieces [Tut63]. In his pioneering work Tutte showed how to compute vertex positions by solving a system of linear equations: the method applies to a 3-connected planar graph and the resulting drawing is guaranteed to be crossing-free, also allowing to fix the positions of outer vertices (which are mapped to the vertices of a given convex polygon). The solution can be also reformulated in terms of a system of springs converging to an equilibrium position, and has inspired a huge number of force-directed embedding algorithms (the interested reader can find a

<footnote n="1">¹ The contributions of this chapter are originated from the collaborations with Eric Fusy and Olivier Devillers [CDF18b], together with our students Gaspard Denis [CDF18a] and Anatolii Kostrygin [CFK14].</footnote>
<figure><img src="image_72.png" /><figcaption>Figure 5.2: Comparison of planar layouts (all layouts are obtained with our Java implementations): the Tutte embedding is compared to the FPP algorithm and the Schnyder drawing. The pictures above show the layouts of a planar random triangulation of size $n = 100$ and a triangle mesh (the fish graph, top pictures). For the sake of readability the FPP layout is re-scaled (its grid size is originally $2n \times n$).</figcaption></figure>

comprehensive survey of force-directed methods in [Kob13]). These methods allows us to obtain very nice layouts achieving several desirable aesthetic criteria, such as uniform edge lengths, low angle distortion or even the preservation of symmetries (see top pictures in Fig. 5.2).

A main common drawback is that one cannot achieve a good vertex resolution, since geometric computations (involving for example linear solvers) lead to vertex coordinates of exponential size. Moreover, they are quite expensive in terms of runtime costs, since their implementation requires iterative linear solvers (for dealing with large sparse matrices) or sometimes non-linear optimization methods, making these approaches slower and less robust than combinatorial graph drawing tools.

**COMBINATORIAL ALGORITHMS.** A solution to the problems above is provided by the so-called *straight-line grid drawings* [FPP90; Kan96; Sch90]: the graph is embedded on a regular grid whose area is typically polynomial with respect to the size of the graph. A further advantage of this approach is that the combinatorial algorithms perform essentially arithmetic computations on integers of bounded magnitude (no roundings are needed).

For the planar case, many classes of algorithms have been proposed to solve this task: in this document we focus on the *face-counting* approach proposed by Schnyder [Sch90] (whose principle is illustrated in the bottom pictures of Figure 5.3) and on the *shift* algorithm described by Fraysseix, Pach, and Pollack [FPP90] (whose steps are sketched in the top pictures of Figure 5.3), both achieving very good vertex resolution (quadratic area) and time complexity (running in linear time in the worst case). Their practical performances are extremely good compared to force-directed methods: using combinatorial algorithms one can deal in real-time with very large graphs, being able of processing several millions of vertices per second. A comparison between the timing costs is given in Figure 5.1.

<figure><img src="image_73.png" /><figcaption>Figure 5.1: Comparison of runtime performances. Timings are expressed in seconds as a function of the size (millions of vertices). The runtimes for the FPP layouts are obtained with our Java implementation where we make use of our reformulation of the shift principle (as described in Section 5.3). For the solution of the linear equations underlying the Tutte embedding, we make use of the Java implementation of the conjugate gradient solver provided by the Matrix Toolkit Java (MTJ) library.</figcaption></figure>
<figure><img src="image_74.png" /><figcaption>Figure 5.3: Top pictures show a planar triangulation endowed with a canonical ordering and the $n-2$ steps of the FPP algorithm [FPP90] that embeds a graph with $n$ vertices on a grid of size $2n \times n$. This algorithm relies on a *shift principle*: we proceed incrementally by adding vertices according to the canonical ordering. At each step the drawing is *stretched* horizontally by adding two vertical bands of width 1, and the new vertex is placed on the outer face at the intersection of two rays having slopes +1 and -1. A detailed description of the shift principle will be provided later in this chapter: note that the FPP layout can be recovered as a special case using our algorithm for cylindrical triangulations presented in Section 5.3. (Bottom) The Schnyder drawing relies on a face-counting principle: the location of a given inner vertex $v$ is defined in terms of barycentric coordinates with respect to the outer vertices: more precisely, $v$ is located at the barycentric combination $\sum_{i \in \{0,1,2\}} \frac{|R_i(v)|}{2n-5} \mathbf{V}_i$, where $|R_i(v)|$ is the number of faces belonging to the region $R_i(v)$ (as defined in Section 2.2.1) and $2n-5$ is the total number of inner faces.</figcaption></figure>

Unfortunately, the resulting layouts are rather unpleasing and fail to achieve some basic aesthetic criteria that help readability: they often have long edges and large clusters of tiny triangles, as illustrated by the pictures in Fig. 5.2.

## 5.2 DRAWINGS HIGHER GENUS GRAPHS: RELATED WORKS

While there is a large literature on planar layouts, the problem of drawing graphs on surfaces has been addressed less frequently from both the theoretical and algorithmic point of view.

**DRAWINGS HIGHER GENUS GRAPHS: LAYOUT SETTING.** For drawing higher genus graphs most existing works [WKS01; GGT06; Moh96; MR98; Cha+12; DGK11; GL14; Zit94] consider the planar (periodic) setting: for instance, in the case of toroidal maps, the main goal is to obtain crossing-free layouts on the flat torus.

Assume from now on that $w$ and $h$ are positive integers. For a cylindrical map $G$, a *periodic straight-line drawing* of $G$ of width $w$ and height $h$ is a crossing-free straight-line drawing (edges are drawn as segments, two edges can meet only at common end-points) of $G$ on the flat cylinder of width $w$ and height $h$, such that the vertex-coordinates are in $\mathbb{Z}/w\mathbb{Z} \times [0..h]$ (i.e. coordinates are integers). Similarly, for a toroidal map $G$, a *periodic*
<figure><img src="image_75.png" /><figcaption>Figure 5.4: (a) A toroidal triangulation $G$; (b) a periodic straight-line drawing of $G$ which is not straight-frame; (c) a non-periodic straight-frame drawing of $G$ (where $G$ is planarly unfolded using a cut-graph); (d) a periodic straight-frame drawing of $G$.</figcaption></figure>

straight-line drawing of $G$ of width $w$ and height $h$ is a crossing-free straight-line drawing of $G$ on the flat torus of width $w$ and height $h$, such that the vertex-coordinates are in $\mathbb{Z}/w\mathbb{Z} \times \mathbb{Z}/h\mathbb{Z}$.

Sometimes the layout is required to satisfy some stronger aesthetic constraints: a *straight-frame* drawing of a toroidal graph $G$ is a planar straight-line drawing of $G$ such that the outer face contour is an axis-aligned rectangle, corresponding to a canonical polygonal scheme of $G$ (the graph is cut along fundamental cycles, whose vertices and edges are placed on horizontal and vertical lines respectively).

Pictures (b) and (d) of Fig. 5.4 show two periodic straight-line drawings of the same graph. Pictures (c) and (d) of Fig. 5.4 correspond to straight-frame drawings: the example in (b) corresponds to a non-periodic drawing since only the relative order of the vertices on the outer face is preserved (vertices consecutive on a fundamental cycle are also consecutive on the boundary).

### 5.2.1 Grid-drawings of toroidal graphs: combinatorial algorithms

**FACE-COUNTING APPROACH.** A recent and elegant method for drawing toroidal graphs with polynomial grid size is the algorithm of Gonçalves and Lévêque [GL14], which is an adaptation of Schnyder's drawing principles to the torus and relies on the properties of crossing Schnyder woods (defined in Section 3.4). It achieves both the periodicity requirement and polynomial grid-size: more precisely, the size of the periodic regular grid is $O(n^2) \times O(n^2)$ for simple toroidal triangulations (no loops or multiple edges) and is $O(n^4) \times O(n^4)$ for essentially simple (simple in the periodic representation) toroidal triangulations. Gonçalves and Lévêque also extend these ideas to 3-connected toroidal maps (similarly, Schnyder woods for plane triangulations have been extended to plane 3-connected maps [Felo1]), but as opposed to the planar case [Felo1], the periodic drawings of 3-connected toroidal maps they obtain do not necessarily have the desired convexity property.

**FPP LAYOUT OF THE PLANARIZED GRAPH.** Recently some methods for the straight-line planar drawing of genus $g$ graphs with polynomial grid area $O(n^3)$ in the worst case have been described [Cha+12; DGK11]. Such methods unfold the graph in the plane along a *cut-graph* and then apply the incremental approach of the FPP algorithm to obtain a straight-frame drawing of the graph. However, these methods do not yield easily periodic representations: for example, in the case of a torus, the boundary vertices might not be aligned, so that the drawing does not give rise to a periodic drawing.

While here we focus on combinatorial algorithms we should point out that some of the numerical algorithms for graph drawing can be used, or easily extended, to deal with higher genus graphs (for instance Kobourov and Wampler [KW05] show how to make use of force-directed layouts in the non-euclidean setting).
Nevertheless the decomposition underlying this approach is interesting and inspired our works on toroidal and spherical drawings (see Sections 5.4 and 5.5), where we can overcome the alignment problem.

## 5.3 OUR CONTRIBUTION: PERIODIC TOROIDAL DRAWINGS

In order to obtain periodic drawings of toroidal maps, we first compute a pair of parallel non-contractible cycles defined a so-called tambourine (as described in Section 2.1.2): the removal of the tambourine leads to a cylindrical map with two inner and outer boundaries, denoted $\Gamma_{\text{inn}}$ and $\Gamma_{\text{ext}}$. The first problem to address is thus to get a periodic straight-line drawings of a cylindrical map: the solution for the triangulated case is detailed below.

### 5.3.1 Drawing cylindrical simple triangulations (with no chord at $\Gamma_{\text{inn}}$).

Here we provide a detailed description of the algorithm for dealing with a cylindrical simple triangulation $G$ with no chord at $\Gamma_{\text{inn}}$ (the more general case, allowing chords at $\Gamma_{\text{inn}}$, as well as multiple edges and loops will be sketched later).

We first compute a canonical ordering of $G$ as described in Section 3.3, and then draw $G$ in an incremental way. We start with a cylinder of width $2|\Gamma_{\text{inn}}|$ and height 0 (i.e., a circle of length $2|\Gamma_{\text{inn}}|$) and draw the vertices of $\Gamma_{\text{inn}}$ equally spaced on the circle: space 2 between two consecutive vertices<fnref n="2" />.

Then the strategy for each $k \ge 1$ is to compute the drawing of $G_k$ out of the drawing of $G_{k-1}$. Note that the set of vertices on the boundary cycle of $G_{k-1}$, denoted $B_{k-1}$, that are neighbours of $v_k$ forms a path $\gamma$ on $B_{k-1}$. Traversing $\gamma$ with the outer face of $G_{k-1}$ to the left, let $e_\ell$ be the first edge of $\gamma$ and $e_r$ be the last edge of $\gamma$ (note that $e_\ell = e_r$ if $v_k$ has only two neighbours on $B_{k-1}$). Let also $a_k$ be the starting vertex and let $b_k$ be the ending vertex of $\gamma$. Two cases can occur.

(1) If, in the drawing of $G_{k-1}$ obtained so far, slope($e_\ell$) < 1 and slope($e_r$) > -1, then we can directly insert $v_k$ in the drawing. We place $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.

(2) If slope($e_\ell$) = 1 or slope($e_r$) = -1, then we cannot directly insert $v_k$ as done in Case (1), because the edges $e_\ell$ and $\{a_k, v_k\}$ would overlap if slope($e_\ell$) = 1, or the edges $e_r$ and $\{b_k, v_k\}$ would overlap if slope($e_r$) = -1. We first have to perform stretching operations (thereby increasing the cylinder width by 2) to make the slopes of $e_\ell$ and $e_r$ smaller than 1 in absolute value. Define the x-span of an edge $e$ in the cylindrical drawing as the number of columns $[i, i+1] \times [0, +\infty)$ that meet the interior of $e$ (we have no need for a more complicated definition since, in our drawings, a column will never meet an edge more than once). Consider the dual forest $F^*$ for the canonical ordering restricted to $G_{k-1}$ (recall its definition given in Section 3.3). Let $P_\ell$ (resp. $P_r$) be the root-path of $e_\ell^*$ (resp. $e_r^*$) in $F^*$. We stretch the cylinder by inserting a vertical strip of length 1 along $P_\ell$ and another along $P_r$, see Fig. 5.5. This comes down to increasing by 1 the x-span of each edge of $G_{k-1}$ dual to an edge in $P_\ell$, and then increasing by 1 the x-span of each edge dual to an edge in $P_r$ (note that $P_\ell$ and $P_r$ are not necessarily disjoint, in which case the x-span of an edge dual to an edge in

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

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

<figure><img src="image_78.png" /><figcaption>Figure 5.5: One step of the incremental algorithm for drawing cylindrical triangulations. Two vertical strips of width 1 (each one along a path in the dual forest) are inserted in order to make the slopes of $e_\ell$ and $e_r$ smaller than 1 in absolute value. Then the new vertex and its edges connected to the upper boundary can be drawn in a planar way.</figcaption></figure>

<footnote n="2">² It is also possible to start with any configuration of points on a circle such that any two consecutive vertices are at even distance.</footnote>