A Scalable Parallel Force-Directed Graph Layout Algorithm

Abstract

Understanding the structure, dynamics, and evolution of large graphs is becoming increasingly important in a variety of fields. The demand for visual tools to aid in this process is rising accordingly. Yet, many algorithms that create good representations of small and medium-sized graphs do not scale to larger graph sizes. The exploitation of the massive computational power provided by parallel and distributed computing is a natural progression for handling important problems such as large graph layout. In this paper, we present a scalable parallel graph layout algorithm based on the force-directed model. Our algorithm requires minimal pre-processing and achieves scalability by conducting the layout computation in stages - a portion of the graph at a time, and decreasing the amount of inter-processor communication as the layout computation progresses. We provide the implementation details of our algorithm, evaluate its performance and scalability, and compare the visual quality of the resulting drawings against some of the classic and the fastest algorithms for the layout of general graphs.