ContactPerson: huazhang@cse.buffalo.edu Remote host: pollux.cse.buffalo.edu ### Begin Citation ### Do not delete this line ### %R 2003-06 %U /home/mthgrad/huazhang/drawing.ps %A "Zhang, Huaming %A He, Xin" %T Canonical Ordering Tree and Its Applications in Graph Drawing %D May 30, 2003 %I Department of Computer Science and Engineering, SUNY Buffalo %K graph, canonical ordering tree, grid embedding, visibility representation %X We study the properties of Schnyder's realizers and canonical ordering trees of plane graphs. Based on these newly discovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First we show that G has a visibility representation with height at most 15n/16. This improves the previous best bound of (n-1). Second, we show that every plane graph G has a straight-line grid embedding on an (n-\Delta_0-1) \times (n-\Delta_0-1) grid, where \Delta_0 is the number of cyclic faces of G with respect to its minimum realizer. This improves the previous best bound of (n-1) \times (n-1). We also study the properties of the regular edge labeling of 4-connected plane triangulation. Based on these properties, we show that every such a graph has a canonical ordering tree with at most (n+1)/2 leaves. This improves the previously known bound of (2n+1)/3. We show that every 4-connected plane graph has a visibility representation with height at most (3n)/4. All drawings discussed in this paper can be obtained in linear time.