Canonical Ordering Trees and Their Applications in Graph Drawing

We study the properties of Schnyders 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 - ₀ - 1) × (n - ₀ - 1) grid, where ₀ is the number of cyclic faces of G with respect to its minimum realizer. This improves the previous best bound of (n - 1) × (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.