Canonical Ordering Trees and Their Applications in Graph Drawing |
| |
Authors: | Huaming Zhang Xin He |
| |
Institution: | (1) Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA |
| |
Abstract: | 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 - 0 - 1) × (n - 0 - 1) grid, where 0 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|