Schnyder decompositions for regular plane graphs and application to drawing

DOI10.1007/S00453-011-9514-5zbMATH Open1239.05038arXiv1007.2484OpenAlexW1552343706MaRDI QIDQ2429329FDOQ2429329

Authors: Olivier Bernardi, Éric Fusy 

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Abstract: Schnyder woods are decompositions of simple triangulations into three edge-disjoint spanning trees crossing each other in a specific way. In this article, we define a generalization of Schnyder woods to $d$-angulations (plane graphs with faces of degree $d$) for all $dgeq3$. A emph{Schnyder decomposition} is a set of $d$ spanning forests crossing each other in a specific way, and such that each internal edge is part of exactly $d-2$ of the spanning forests. We show that a Schnyder decomposition exists if and only if the girth of the $d$-angulation is $d$. As in the case of Schnyder woods ($d=3$), there are alternative formulations in terms of orientations ("fractional" orientations when $dgeq5$) and in terms of corner-labellings. Moreover, the set of Schnyder decompositions on a fixed $d$-angulation of girth $d$ is a distributive lattice. We also show that the structures dual to Schnyder decompositions (on $d$-regular plane graphs of mincut $d$ rooted at a vertex $v^{*}$) are decompositions into $d$ spanning trees rooted at $v^{*}$ such that each edge not incident to $v^{*}$ is used in opposite directions by two trees. Additionally, for even values of $d$, we show that a subclass of Schnyder decompositions, which are called even, enjoy additional properties that yield a reduced formulation; in the case d=4, these correspond to well-studied structures on simple quadrangulations (2-orientations and partitions into 2 spanning trees). In the case d=4, the dual of even Schnyder decompositions yields (planar) orthogonal and straight-line drawing algorithms. For a 4-regular plane graph $G$ of mincut 4 with $n$ vertices plus a marked vertex $v$, the vertices of $$ are placed on a $(n-1)imes(n-1)$ grid according to a permutation pattern, and in the orthogonal drawing each of the $2n-2$ edges of $$ has exactly one bend. Embedding also the marked vertex $v$ is doable at the cost of two additional rows and columns and 8 additional bends for the 4 edges incident to $v$. We propose a further compaction step for the drawing algorithm and show that the obtained grid-size is strongly concentrated around $25n/32imes25n/32$ for a uniformly random instance with $n$ vertices.

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

Recommendations

• On the structure of Schnyder woods on orientable surfaces
• Schnyder Woods and Orthogonal Surfaces
• Schnyder woods and orthogonal surfaces
• Schnyder woods for higher genus triangulated surfaces (abstract)
• Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations

zbMATH Keywords

straight-line drawingNash-Williams theoremorthogonal drawingSchnyder woodsforest decomposition4-regular mapSchnyder labelling

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Planar graphs and poset dimension
• Lattice structures from planar graphs
• Title not available (Why is that?)
• A better heuristic for orthogonal graph drawings
• Drawing planar graphs using the canonical ordering
• Dissections and trees, with applications to optimal mesh encoding and to random sampling
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Optimal coding and sampling of triangulations
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• Bijections for Baxter families and related objects
• Baxter permutations and plane bipolar orientations
• On topological aspects of orientations
• Convex drawings of planar graphs and the order dimension of 3-polytopes
• Planar graphs, via well-orderly maps and trees
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• 4-labelings and grid embeddings of plane quadrangulations
• Binary labelings for plane quadrangulations and their relatives
• Intervals in Catalan lattices and realizers of triangulations
• Bijective counting of plane bipolar orientations and Schnyder woods
• ULD-lattices and \(\Delta \)-bonds
• New Lower Bounds For Orthogonal Drawings
• Lower bounds for planar orthogonal drawings of graphs
• Asymptotic enumeration of orientations

Cited In (10)

• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Contact representations of graphs in 3D
• Schnyder woods, \(\mathrm{SLE}_{16}\), and Liouville quantum gravity
• Unified bijections for maps with prescribed degrees and girth
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• 4-labelings and grid embeddings of plane quadrangulations
• A Schnyder-type drawing algorithm for 5-connected triangulations
• Bijections for generalized Tamari intervals via orientations
• Binary labelings for plane quadrangulations and their relatives
• A bijection for essentially 3-connected toroidal maps

This page was built for publication: Schnyder decompositions for regular plane graphs and application to drawing

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