GRIP: Graph dRawing with Intelligent Placement
GRIP is designed for drawing large graphs and uses a novel
multi-dimensional force-directed method together with fast energy
function minimization. The algorithm underlying the system employs a
simple recursive coarsening scheme. Rather than being placed at
random, vertices are placed intelligently, several at a time, at
locations close to their final positions. The running time and space
complexity of the system are near linear. The implementation is in C
using OpenGL for 3D viewing. GRIP allows for drawing graphs with tens
of thousands of vertices in under one minute on a mid-range PC. To the
best of the authors' knowledge, GRIP surpasses the fastest previous
algorithms. However, speed is not achieved at the expense of quality
as the resulting drawings are quite aesthetically pleasing.
The current version of GRIP was implemented by Roman Yusufov as an honors
thesis at the CS Department of
University of Arizona and was completed in December 2001.
Here are some sample drawings produced by GRIP. You can also view a demo
of GRIP in action.
