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.


[ Home | Research | Papers | Teaching | CV | Colleagues | Links | U of A | U of A CS ]