Daniel Tunkelang

A Numerical Optimization Approach to General Graph Drawing Degree Type: Ph.D. in Algorithms, Combinatorics and Optimization
Advisor(s): Daniel Sleator
Graduated: December 1998

Abstract:

Graphs are ubiquitous, finding applications in domains ranging from software engineering to computational biology. While graph theory and graph algorithms are some of the oldest, most studied fields in computer science, the problem of visualizing graphs is comparatively young. This problem, known as graph drawing, is that of transforming combinatorial graphs into geometric drawings for the purpose of visualization.

Most published algorithms for drawing general graphs model the drawing problem with a physical analogy, representing a graph as a system of springs and other physical elements and then simulating the relaxation of this physical system. Solving the graph drawing problem involves both choosing a physical model and then using numerical optimization to simulate the physical system.

In this dissertation, we improve on existing algorithms for drawing general graphs. The improvements fall into three categories: speed, drawing quality, and flexibility. We improve the speed using known techniques from both the many-body work in astrophysics and the numerical optimization literature. We improve drawing quality both by making our physical model more comprehensive than those in the literature and by employing heuristics in our optimization procedure to avoid poor local minima. Finally, we improve the flexibility of existing approaches both by cleanly separating the physical model from the optimization procedure and by allowing the model to include a broad class of constraints.

We are able to demonstrate some of our improvements through theoretical analysis. To demonstrate the others, we use an implementation of our approach in the Java programming language.

Thesis Committee:
Daniel Sleator (Chair)
Paul Heckbert
Bruce Maggs
Omar Ghattas (Civil and Environmental Engineering)
Mark Wegman (IBM T . J. Watson Research Center)

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
Visualization, graph drawing, numerical optimization, force-directed