Grand Schnyder Woods

arXiv2303.15630MaRDI QIDQ6431056FDOQ6431056

Shizhe Liang, Éric Fusy, Olivier Bernardi

Publication date: 27 March 2023

Abstract: We define a far-reaching generalization of Schnyder woods which encompasses many classical combinatorial structures on planar graphs. Schnyder woods are defined for planar triangulations as certain triples of spanning trees covering the triangulation and crossing each other in an orderly fashion. They are of theoretical and practical importance, as they are central to the proof that the order dimension of any planar graph is at most 3, and they are also underlying an elegant drawing algorithm. In this article we extend the concept of Schnyder wood well beyond its original setting: for any integer d we define a ``grand-Schnyder structure for (embedded) planar graphs which have faces of degree at most d and non-facial cycles of length at least d. We prove the existence of grand-Schnyder structures, provide a linear construction algorithm, describe 4 different incarnations (in terms of tuples of trees, corner labelings, weighted orientations, and marked orientations), and define a lattice for the set of grand Schnyder structures of a given planar graph. We show that the grand-Schnyder framework unifies and extends several classical constructions: Schnyder woods and Schnyder decompositions, regular edge-labelings (a.k.a. transversal structures), and Felsner woods.

This page was built for publication: Grand Schnyder Woods

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