View Related Documents

Abstract

We study the properties of Schnyderrsquos 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 lceil 15n/16 rceil. 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 - delta0 - 1) × (n - delta0 - 1) grid, where delta0 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 lceil (n + 1)/2 rceil leaves. This improves the previously known bound of lfloor (2n + 1)/3 rfloor. We show that every 4-connected plane graph has a visibility representation with height at most lceil 3n/4 rceil. All drawings discussed in this paper can be obtained in linear time.

Fulltext Preview

Image of the first page of the fulltext document