Orienting triangulations

DOI10.1002/JGT.22005zbMATH Open1350.05128arXiv1412.4979OpenAlexW2526558715MaRDI QIDQ2833256FDOQ2833256

Boris Albar, Kolja Knauer, Daniel Gonçalves

Publication date: 17 November 2016

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: We prove that any triangulation of a surface different from the sphere and the projective plane admits an orientation without sinks such that every vertex has outdegree divisible by three. This confirms a conjecture of Bar'at and Thomassen and is a step towards a generalization of Schnyder woods to higher genus surfaces.

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

zbMATH Keywords

triangulationsorientationssurfaces

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Bijective counting of tree-rooted maps and shuffles of parenthesis systems
• Planar graphs and poset dimension
• Lattice structures from planar graphs
• Claw‐decompositions and tutte‐orientations
• On Triangle Contact Graphs
• Convex drawings of planar graphs and the order dimension of 3-polytopes
• Schnyder woods for higher genus triangulated surfaces, with applications to encoding
• Intervals in Catalan lattices and realizers of triangulations
• Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations

Cited In (4)

• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• Pushing vertices and orienting edges
• Determining the orientation of closed planar curves
• Encoding toroidal triangulations

This page was built for publication: Orienting triangulations

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