Back to Search
Start Over
Canonical Ordering Trees and Their Applications in Graph Drawing.
- Source :
- Discrete & Computational Geometry; Feb2005, Vol. 33 Issue 2, p321-344, 73p
- Publication Year :
- 2005
-
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 - d <subscript>0</subscript> - 1) × (n - d <subscript>0</subscript> - 1) grid, where d <subscript>0</subscript> 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- GRAPHIC methods
GEOMETRICAL drawing
LEAST squares
MECHANICAL drawing
Subjects
Details
- Language :
- English
- ISSN :
- 01795376
- Volume :
- 33
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- Discrete & Computational Geometry
- Publication Type :
- Academic Journal
- Accession number :
- 17138269