  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 $d\geq 3$. 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 $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 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 $G\backslash v$ are placed on a $(n-1) \times
(n-1)$ grid according to a permutation pattern, and in the orthogonal drawing
each of the $2n-2$ edges of $G\backslash v$ 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/32\times 25n/32$ for a uniformly
random instance with $n$ vertices.
