Abstract: This paper introduces the orderly pair of connected planar graphs. We give a linear-time algorithm to obtain 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.
This paper, by Yi-Ting Chiang, Ching-Chi Lin, and Hsueh-I Lu, was presented at the 2001 Symposium on Discrete Algorithms.