Today I read a paper titled “Orderly Spanning Trees with Applications”
The abstract is:
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.