Orderly spanning trees with applications

Abstract

We introduce and study orderly spanning trees of plane graphs. This algorithmic tool generalizes 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 orderly pair for any connected planar graph G, consisting of an embedded planar graph H isomorphic to 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 algorithm for computing an area-optimal 2-visibility drawing of a planar graph, and ( 3) the most compact known encoding of a planar graph with O(1)-time query support. All algorithms in this paper run in linear time.