Orderly Spanning Trees with Applications to Graph Encoding and Graph Drawing
Yi-Ting Chiang, Ching‐Chi Lin, Hsueh-I Lu · arXiv (Cornell University) · 2001
The canonical ordering for triconnected planar graphs is a powerful method for designing graph algorithms. This paper introduces the orderly pair of connected planar graphs, which extends the concept of canonical ordering to planar graphs not required to be triconnected. Let G be a connected planar graph. We give a linear-time algorithm that obtains an orderly pair (H, T) of G, where H is a planar embedding of G, and T is an orderly spanning tree of H. As applications, we show that the technique of orderly spanning trees yields (i) the best known encoding of G with query support, and (ii) the first area-optimal 2-visibility drawing of G. 1