Home | Issues | About JGAA | Instructions for Authors |
Selected Papers from the 2000 Symposium on Graph Drawing
DOI: 10.7155/jgaa.00052
GRIP: Graph Drawing with Intelligent Placement
Pawel Gajer and
Stephen G. Kobourov
Vol. 6, no. 3, pp. 203-224, 2002. Regular paper.
Abstract This paper describes a system for Graph dRawing with Intelligent
Placement, GRIP\xspace. The system 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. The GRIP\xspace system 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\xspace surpasses the fastest
previous algorithms. However, speed is not achieved at the expense
of quality as the resulting drawings are quite aesthetically
pleasing.
|
Journal Supporters
|