ICS Theory Group

ICS 269, Spring 2002: Theory Seminar

22 November 2002:
Title: Orderly Spanning Trees with Applications to Graph Encoding and Graph Drawing
Speaker: Gwendoline Chien

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.