Canonical Ordering Trees and Their Applications in Graph Drawing
Canonical Ordering Trees and Their Applications in Graph Drawing
复制标题
规范排序树及其在绘图中的应用
DOI：
--
复制
发表时间：
2005
影响因子：
0.8
通讯作者：
Xin He
中科院分区：
文献类型：
--
作者：
Huaming Zhang;Xin He
摘要
研究了平面图的Schnyder实现子和标准序树的性质。基于这些新的
发现的性质，我们获得了两种风格的紧凑图的任何平面图G有n个顶点。首先，我们证明G有一个
高度最大为15 n/16 m的可见性表示。这改进了先前的最佳界
的（n - 1）。其次，我们证明了每个平面图G都有一个直线格
嵌入在（n - δ0 - 1）×（n - δ0 - 1）网格上，其中δ0是G关于其
最小实现器这改进了（n - 1）×（n - 1）的先前最佳界。
本文还研究了4-连通平面三角剖分的正则边标号的性质。基于这些
性质，我们证明了每一个这样的图都有一个不超过n（n + 1）/2个叶子的标准序树。
这改进了先前已知的<$（2n + 1）/3 <$的界。
我们证明了每个4-连通平面图都有可见性
高度不超过3 n/4 m的表示。
本文讨论的所有绘图都可以在线性时间内获得。
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.