Encoding toroidal triangulations

DOI10.1007/S00454-016-9832-0zbMATH Open1370.68296arXiv1507.05461OpenAlexW2963609981MaRDI QIDQ527433FDOQ527433

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)

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

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

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)

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)

Cites Work

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

Cited In (9)

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

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)