Orderly Spanning Trees with Applications
<|reference_start|>Orderly Spanning Trees with Applications: 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.<|reference_end|>
@article{chiang2001orderly,
    title={Orderly Spanning Trees with Applications},
    author={Yi-Ting Chiang, Ching-Chi Lin, and Hsueh-I Lu},
    journal={SIAM Journal on Computing 34(4): 924-945 (2005)},
    year={2001},
    doi={10.1137/S0097539702411381},
    archivePrefix={arXiv},
    eprint={cs/0102006},
    primaryClass={cs.DS cs.DM}
}