Abstract
Graph Visualization focuses on visualizing (drawing) graphs such that it is easy to understand the structure of a graph from its visualization. It has applications in various fields such as Software Engineering, Databases, and Biology. The degree of a graph is equal to the maximum number of edges incident on a vertex. A grid drawing of a graph is one that assigns integer coordinates to its vertices. Grid drawings guarantee a minimum unit distance between vertices, and can be rendered on a display surface such as computer screen without any distortions due to rounding-off errors. A straight-line drawing of a graph is one, where each edge is drawn as a single line-segment. A planar drawing of a graph is one that has no edge-crossings. For a drawing to display a graph better, it should have few edge-crossings and few edge-bends. Ideally, the drawing should be planar and straightline. Moreover, it should have small area, so that it can be displayed even on small display surfaces. The aspect ratio of a graph is the ratio of the width and height of the drawing. Giving the users control over the aspect ratio of a drawing allows them to display the drawing in different kinds of display surfaces with different aspect ratios. The optimal use of screen space is achieved by minimizing the area of the drawing and by providing user-controlled aspect ratio.

An ordered tree T is one with a pre-specified counterclockwise ordering of the edges incident on each node. Ordered trees arise commonly in practice. Examples of ordered trees include binary search trees, arithmetic expression trees, and B-trees. An order-preserving drawing of T is one in which the counterclockwise ordering of the edges incident on a node is the same as their pre-specified ordering in T. Ordered trees are generally drawn using order-preserving planar straight-line grid drawings, as any undergraduate textbook on datastructures will show.

In this thesis, we have focused on constructing area-efficient planar straight-line grid drawings of trees and outerplanar graphs, which are important categories of graphs. Our results include the following: 1. A degree-d tree with n nodes, where $d = O(n^{\delta})$ and $0 \le \delta < 1/2$ is a constant, admits a planar straight-line grid drawing with optimal linear area and arbitrary aspect ratio. In particular, this result implies that a binary tree can be drawn in such a fashion in optimal linear area.

2. An ordered tree with n nodes admits an order-preserving planar straight-line grid drawing with O(n log n) area.

{'paper_id': '11450866', 'title': 'Adrian Rusu', 's2_url': 'https://api.semanticscholar.org/CorpusID:11450866', 'source': 'S2ORC'}