Lattice Structures from Planar Graphs
Stefan Felsner
Source abstract
The set of all orientations of a planar graph with prescribed outdegrees carries the structure of a distributive lattice. This general theorem is proven in the first part of the paper. In the second part the theorem is applied to show that interesting combinatorial sets related to a planar graph have lattice structure: Eulerian orientations, spanning trees and Schnyder woods. For the Schnyder wood application some additional theory has to be developed. In particular it is shown that a Schnyder wood for a planar graph induces a Schnyder wood for the dual.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.