Schnyder woods for higher genus triangulated surfaces, with applications to encoding

DOI10.1007/s00454-009-9169-zzbMath1210.05162arXiv0904.2776OpenAlexW1973111922MaRDI QIDQ834610

Thomas Lewiner, Luca Castelli Aleardi, Éric Fusy

Publication date: 27 August 2009

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

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

zbMATH Keywords

triangulationsgraph encodingSchnyder woodshigher genus surfaces

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Planar graphs; geometric and topological aspects of graph theory (05C10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Graph algorithms (graph-theoretic aspects) (05C85) Polyhedral manifolds (52B70)

Related Items (7)

A simple routing algorithm based on Schnyder coordinates ⋮ A note on Schnyder's theorem ⋮ Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators ⋮ Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations ⋮ On succinct greedy drawings of plane triangulations and 3-connected plane graphs ⋮ Orienting Triangulations ⋮ Clustering analysis of a dissimilarity: a review of algebraic and geometric representation

Uses Software

• Edgebreaker

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the succinct representation of graphs
• Optimal coding and sampling of triangulations
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Succinct representations of planar maps
• Intervals in Catalan lattices and realizers of triangulations
• Planar graphs and poset dimension
• A pattern for the asymptotic number of rooted maps on surfaces
• Optimal discrete Morse functions for 2-manifolds
• Optimally cutting a surface into a disk
• Optimal system of loops on an orientable surface
• Short encodings of planar graphs and maps
• A note on finding the bridges of a graph
• Lattice structures from planar graphs
• Drawing planar graphs using the canonical ordering
• Planar graphs, via well-orderly maps and trees
• Edge Partition of Toroidal Graphs into Forests in Linear Time
• Asymptotic Enumeration of Constellations and Related Families of Maps on Orientable Surfaces
• A Bijection for Rooted Maps on Orientable Surfaces
• Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings
• Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
• Computing a canonical polygonal schema of an orientable triangulated surface
• Succinct Representation of Labeled Graphs
• Algorithms and Data Structures
• Depth-First Search and Linear Graph Algorithms
• A Census of Planar Maps
• On topological aspects of orientations
• Convex drawings of planar graphs and the order dimension of 3-polytopes

This page was built for publication: Schnyder woods for higher genus triangulated surfaces, with applications to encoding