Multi-Level Graph Layout on the GPU
Technion, Israel Institute of Technology
IEEE Transactions on Visualization and Computer Graphics, Vol. 13, No. 6. (2007), pp. 1310-1319.
@article{frishman2007multi,
title={Multi-level graph layout on the GPU},
author={Frishman, Y. and Tal, A.},
journal={IEEE transactions on visualization and computer graphics},
pages={1310–1319},
issn={1077-2626},
year={2007},
publisher={Published by the IEEE Computer Society}
}
This paper presents a new algorithm for force directed graph layout on the GPU. The algorithm, whose goal is to compute layouts accurately and quickly, has two contributions. The first contribution is proposing a general multi-level scheme, which is based on spectral partitioning. The second contribution is computing the layout on the GPU. Since the GPU requires a data parallel programming model, the challenge is devising a mapping of a naturally unstructured graph into a well-partitioned structured one. This is done by computing a balanced partitioning of a general graph. This algorithm provides a general multi-level scheme, which has the potential to be used not only for computation on the GPU, but also on emerging multi-core architectures. The algorithm manages to compute high quality layouts of large graphs in a fraction of the time required by existing algorithms of similar quality. An application for visualization of the topologies of ISP (Internet Service Provider) networks is presented.
November 5, 2010 by hgpu
