| 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. |
