Encoding toroidal triangulations

2015/07/20 by Despré, Vincent, Gonçalves, Daniel, Lévêque, Benjamin
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1507.05461

Abstract

Poulalhon and Schaeffer introduced an elegant method to linearly encode a planar triangulation optimally. The method is based on performing a special depth-first search algorithm on a particular orientation of the triangulation: the minimal Schnyder wood. Recent progress toward generalizing Schnyder woods to higher genus enables us to generalize this method to the toroidal case. In the plane, the method leads to a bijection between planar triangulations and some particular trees. For the torus we obtain a similar bijection but with particular unicellular maps (maps with only one face).

Related

• Toroidal maps : Schnyder woods, orthogonal surfaces and straight-line representations
• Generalization of Schnyder woods to orientable surfaces and applications
• Schnyder woods for higher genus triangulated surfaces, with applications to encoding
• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• A bijection for essentially 4-connected toroidal triangulations