Computer Science Department
School of Computer Science, Carnegie Mellon University
A Numerical Optimization Approach to General Graph Drawing
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.