Encoding toroidal triangulations

DOI10.1007/S00454-016-9832-0MaRDI QIDQ527433zbMATH OpenOpenAlexFDO

Authors Vincent Despré, Benjamin Lévêque, Daniel Gonçalves

Publication date 11 May 2017

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.05461

zbMATH Keywords

distributive latticesSchnyder woodsalpha-orientationsbijective encodingPoulalhon and Schaeffer's methodtoroidal triangulationsunicellular maps

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10)

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).

Recommendations

• Schnyder woods for higher genus triangulated surfaces, with applications to encoding
• scientific article; zbMATH DE number 2038776
• Optimal coding and sampling of triangulations
• On the structure of Schnyder woods on orientable surfaces
• Schnyder woods for higher genus triangulated surfaces (abstract)

Cites work

• scientific article; zbMATH DE number 1962839 (Why is no real title available?)
• A Bijection for Rooted Maps on Orientable Surfaces
• A bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• A generic method for bijections between blossoming trees and planar maps
• A new combinatorial identity for unicellular maps, via a direct bijective approach
• Bijective counting of tree-rooted maps and shuffles of parenthesis systems
• Drawing planar graphs using the canonical ordering
• Graphs, surfaces and homology
• Lattice structures from planar graphs
• On the structure of Schnyder woods on orientable surfaces
• On topological aspects of orientations
• Optimal coding and sampling of triangulations
• Orienting triangulations
• Planar graphs and poset dimension
• Straight-line representations of maps on the torus and other flat surfaces
• Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations
• Uniform random sampling of simple branched coverings of the sphere by itself

Cited in

(9)

• Blossoming bijection for higher-genus maps
• Succinct encoding of binary strings representing triangulations
• A bijection for essentially 4-connected toroidal triangulations
• Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
• A bijection for essentially 3-connected toroidal maps
• Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators
• Bijective proof of the rationality of the generating series of higher-genus maps
• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• Optimal coding and sampling of triangulations

This page was built for publication: Encoding toroidal triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q527433)