Comments: The report file is placed on pollux.
ContactPerson: adirusu@cse.buffalo.edu
Remote host: roc-66-66-57-100.rochester.rr.com
### Begin Citation ### Do not delete this line ###
%R 2003-08
%U /tmp/main.pdf
%A Rusu, Adrian
%T Area-Efficient Grid Drawings of Graphs
%D August 16, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Graph Drawing, Planar, Straight-line, Tree, Outerplanar, Area, Aspect Ratio, Information Visualization, Computational Geometry
%Y Algorithms; Theory
%X The visualization of relational information is concerned with the presentation of
abstract information about relationships between various entities.
It has many applications in diverse domains such as software engineering, biology,
civil engineering, and cartography.
Relational information is typically modeled by an abstract graph, where vertices are
entities and edges represent relationships 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:
\begin{enumerate}
\item An algorithm for producing planar straight-line grid drawings of binary trees
with optimal linear area and with user-defined arbitrary aspect ratio,
\item An algorithm for producing planar straight-line grid drawings of degree-$d$
trees with $n$ nodes, where $d=O(n^{\delta})$ and $0 \le \delta < 1/2$ is a constant,
with optimal linear area and with user-defined arbitrary aspect ratio,
\item 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,
\item 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,
\item An algorithm for producing order-preserving upward planar straight-line grid
drawings of ordered binary trees with optimal $O(n \log n)$ area,
\item 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
\item An algorithm for producing planar straight-line grid drawings of outerplanar
graphs with $n$ vertices and degree $d$ in $O(dn^{1.48})$ area. This result shows for
the first time that a large category of outerplanar graphs, namely those with degree
$d=O(n^{\delta})$, where $0 \le \delta < 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.