The visualization of relational information is concerned with the presentation many applications in diverse domains such as software engineering, biology, civil engineering, and cartography. Relational information is typically modeled between entities. The aim of graph drawing is to automatically produce drawings of graphs which clearly reflect the inherent relational information.; This thesis is primarily concerned with problems related to the automatic generation of area-efficient grid drawings of trees and outerplanar graphs, which are important categories of graphs.; The main achievements of this thesis include: (1) An algorithm for producing planar straight-line grid drawings of binary trees with optimal linear area and with user-defined arbitrary aspect ratio, (2) An algorithm for producing planar straight-line grid drawings of degree-d trees with n nodes, where d = O(nδ) and 0 ≤ δ 1/2 is a constant, with optimal linear area and with user-defined arbitrary aspect ratio, (3) An algorithm which establishes the currently best known upper bound, namely O(n log n), on the area of order-preserving planar straight-line grid drawings of ordered trees, (4) An algorithm which establishes the currently best known upper bound, namely O(n log log n), on the area of order-preserving planar straight-line grid drawings of ordered binary trees, (5) An algorithm for producing order-preserving upward planar straight-line grid drawings of ordered binary trees with optimal O(n log n) area, (6) An algorithm which establishes the trade-off between the area and aspect ratio of order-preserving planar straight-line grid drawings of ordered binary trees, in the case when the aspect ratio is arbitrarily defined by the user, and (7) An algorithm for producing planar straight-line grid drawings of outerplanar graphs with n vertices and degree d in O( dn1.48) area. This result shows for the first time that a large category of outerplanar graphs, namely those with degree d = O(nδ), where 0 ≤ δ 0.52 is a constant, can be drawn in sub-quadratic area.; All our algorithms are time-efficient. More specifically, algorithms 1 and 2 run in O(n log n) time each, and algorithms 3, 4, 5, 6, and 7 run in O( n) time each.
展开▼
机译：关系信息的可视化与多种领域中许多应用程序的表示有关，例如软件工程，生物学，土木工程和制图。关系信息通常在实体之间建模。图形绘制的目的是自动生成清晰反映固有关系信息的图形绘制。本文主要涉及与树木和外平面图的面积有效的网格图的自动生成有关的问题，树和外平面图是图的重要类别。本论文的主要成就包括：（1）一种生成具有最佳线性面积且具有用户定义的任意纵横比的二叉树的平面直线网格图形的算法，（2）一种产生平面直线网格图形的算法具有 n 个节点的度数 d 树，其中 d = O （ n δ）和0≤δ<1/2是一个常数，具有最佳线性区域和用户定义的任意纵横比，（3）建立当前最知名的上限的算法，即< italic> O （ n log n ），在有序树的保序平面直线网格绘图区域上，（4）在保留订单的平面直线网格区域上建立当前最知名的上限，即 O （ n log log n ）有序二叉树的图形，（5）算法f或生成具有最佳 O （ n log n ）面积的有序二叉树的保持订单向上的平面直线网格图，（6）一种算法，在用户任意定义纵横比的情况下，在有序二叉树的保持顺序的平面直线网格图形的面积和纵横比之间进行权衡，以及（7）生成具有 n 顶点和 d 在 O （ dn 1.48 ）区域。该结果首次显示出一大类外平面图，即度数 d = O （ n δ< / super>），其中0≤δ<0.52是常数，可以在次二次区域绘制。我们所有的算法都是省时的。更具体地说，算法1和2分别以 O （ n log n ）时间运行，算法3、4、4、5、6和7个分别以 O （ n ）的时间运行。
展开▼
