English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Schnyder woods are decompositions of simple triangulations into threeedge-disjoint spanning trees crossing each other in a specific way. In thisarticle, we define a generalization of Schnyder woods to $d$-angulations (planegraphs with faces of degree $d$) for all $d\geq 3$. A \emph{Schnyderdecomposition} is a set of $d$ spanning forests crossing each other in aspecific way, and such that each internal edge is part of exactly $d-2$ of thespanning forests. We show that a Schnyder decomposition exists if and only ifthe 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 $d\geq 5$) 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 toSchnyder decompositions (on $d$-regular plane graphs of mincut $d$ rooted at avertex $v^*$) are decompositions into $d$ spanning trees rooted at $v^*$ suchthat each edge not incident to $v^*$ is used in opposite directions by twotrees. Additionally, for even values of $d$, we show that a subclass ofSchnyder decompositions, which are called even, enjoy additional propertiesthat yield a reduced formulation; in the case d=4, these correspond towell-studied structures on simple quadrangulations (2-orientations andpartitions into 2 spanning trees). In the case d=4, the dual of even Schnyderdecompositions yields (planar) orthogonal and straight-line drawing algorithms.For a 4-regular plane graph $G$ of mincut 4 with $n$ vertices plus a markedvertex $v$, the vertices of $G\backslash v$ are placed on a $(n-1) \times(n-1)$ grid according to a permutation pattern, and in the orthogonal drawingeach of the $2n-2$ edges of $G\backslash v$ has exactly one bend. Embeddingalso the marked vertex $v$ is doable at the cost of two additional rows andcolumns and 8 additional bends for the 4 edges incident to $v$. We propose afurther compaction step for the drawing algorithm and show that the obtainedgrid-size is strongly concentrated around $25n/32\times 25n/32$ for a uniformlyrandom instance with $n$ vertices.

Schnyder decompositions for regular plane graphs and application to drawing