  We introduce and study the {\em orderly spanning trees} of plane graphs. This
algorithmic tool generalizes {\em canonical orderings}, which exist only for
triconnected plane graphs. Although not every plane graph admits an orderly
spanning tree, we provide an algorithm to compute an {\em orderly pair} for any
connected planar graph $G$, consisting of a plane graph $H$ of $G$, and an
orderly spanning tree of $H$. We also present several applications of orderly
spanning trees: (1) a new constructive proof for Schnyder's Realizer Theorem,
(2) the first area-optimal 2-visibility drawing of $G$, and (3) the best known
encodings of $G$ with O(1)-time query support. All algorithms in this paper run
in linear time.
