A multi-dimensional approach to force-directed layouts of large graphs

Computational Geometry 29 (2004) 3–18 www.elsevier.com/locate/comgeo A multi-dimensional approach to force-directed layouts of large graphs ✩ Pawel Gajer a , Michael T. Goodrich b , Stephen G. Kobourov c,∗ a Department of Computer Science, Johns Hopkins University, USA b Department of Information and Computer Science, University of California, Irvine CA, USA c Department of Computer Science, University of Arizona, USA Available online 18 May 2004 Communicated by I. Streinu Abstract We present a novel hierarchical force-directed method for drawing large

graphs. Given a graph G = (V,E),the algorithm produces an embedding for G in an Euclidean space E of any dimension. A two or three dimensional drawing of the graph is then obtained by projecting a higher-dimensional embedding into a two or three dimensional subspace of E. Such projections typically result in drawings that are “smoother” and more symmetric than direct drawings in 2D and 3D. In order to obtain fast placement of the vertices of the graph our algorithm employs a multi-scale technique based on a maximal independent set filtration of vertices of the graph. While most existing force-directed algorithms begin with an initial random placement of all the vertices, our algorithm attempts to place vertices “intelligently”, close to their final positions. Other notable features of our approach include a fast energy function minimization strategy and efficient memory management. Our implementation of the algorithm can draw graphs with tens of thousands of vertices using a negligible amount of memory in less than one minute on a 550 MHz Pentium PC. 2004 Elsevier B.V. All rights reserved. Keywords: Large graph drawing; Multi-scale method; High-dimensional embedding; Force-directed method 1. Introduction Graphs are common in many applications, from compilers to networks, from software engineering to databases. Typically, small graphs are drawn manually so that the resulting picture best shows ✩ This research partially supported by NSF under Grant CCR-9625289, and ARO under grant DAAH04-96-1-0013. A preliminary version of this paper appeared in the Proceedings of the 8th Annual Symposium on Graph Drawing, 2000. * Corresponding author. E-mail address: kobourov@cs.arizona.edu (S.G. Kobourov). 0925-7721/$ – see front matter 2004 Elsevier B.V. All rights reserved. doi:10.1016/j.comgeo.2004.03.014 4 P. Gajer et al. / Computational Geometry 29 (2004) 3–18 the underlying relationships. The task of drawing graphs by hand becomes more challenging as the complexity and size of the graphs increases. Graph drawing tools have been the focus of the graph drawing community for at least the last two decades; see [11,30] for comprehensive reviews of the graph drawing field and [44] for work in information visualization. Numerous algorithms have been developed for drawing special classes of graphs such as trees and planar graphs. There are few general purpose graph drawing algorithms, however. Force-directed methods are often the methods of choice for drawing general graphs. Substantial interest in force-directed methods stems from their conceptual simplicity, applicability to general graphs, and typically aesthetically pleasing results. Automated...

Website: www.ics.uci.edu | Filesize: -
No of Page(s): 16
Download A multi-dimensional approach to force-directed layouts of large graphs.pdf