Orientations des triangulations de genre $g\ge 2$

Orienting triangulations of genus $g\ge 2$

In [PS06] the authors revealed a bijection between planar triangulations with $n$ vertices (with no loop, nor multiple edges) with particular trees (roughly these trees have $n-3$ inner nodes, and these nodes have 2 leaves each). As trees are simple to manipulate, this allowed the counting, the optimal encoding (with as few bits as needed), and the design of random generators for planar triangulations.

Recently [DGL15], this work has been extended to toroidal triangulations (with no contractible cycle of length $< 3$). Their proof (such as in the planar case) uses particular orientations of the edges. To extend this work to triangulations of higher genus they ask for orientations such that

a) every vertex has out-degree in $\{3,6,9,\ldots\}$, and

b) every non-contractible closed curve is traversed by arcs in both directions.

It is known that orientations fulfilling a) exist [AGK15]. The goal of this internship is to study the proof in [AGK15] in order to achieve both a) and b). As the proof in [AGK15] actually only applies to triangulations without any loop nor multiple edges, another question is to extend this result to triangulations where non-contractible cycles of length $< 3$ are allowed.

Biblio

[AGK15] B. Albar, D. Gonçalves, K. Knauer, Orienting triangulations, J. of Graph Theory, to appear.

[DGL15] V. Despré, D. Gonçalves, B. Lévêque, Encoding toroidal triangulations, ArXiv:1507.05461.

[PS06] D. Poulalhon, G. Schaeffer, Optimal coding and sampling of triangulations, Algorithmica 46 (2006) 505-527.