Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling

DOI10.1145/1361192.1361196zbMath1451.05230arXiv0810.2608OpenAlexW2034983981MaRDI QIDQ4962712

Gilles Schaeffer, Dominique Poulalhon, Éric Fusy

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

countingbijectioncodingrandom generation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Schnyder woods for higher genus triangulated surfaces, with applications to encoding ⋮ Succinct encoding of binary strings representing triangulations ⋮ Enumeration of corner polyhedra and 3-connected Schnyder labelings ⋮ Enumeration of corner polyhedra and 3-connected Schnyder labelings ⋮ Unified bijections for maps with prescribed degrees and girth ⋮ A bijection for triangulations, quadrangulations, pentagulations, etc. ⋮ Counting colored planar maps: algebraicity results ⋮ Uniform random sampling of planar graphs in linear time ⋮ A bijection for essentially 3-connected toroidal maps ⋮ Fast and compact planar embeddings ⋮ New bijective links on planar maps via orientations ⋮ Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth

This page was built for publication: Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling