A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs

Gajer, Pawel and Goodrich, Michael T. and Kobourov, Stephen G. (2001) A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs. In: Graph Drawing, 2000 , pp. 211-221(Official URL: http://dx.doi.org/10.1007/3-540-44541-2_20).

Full text not available from this repository.

Abstract

We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space \mathbb{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 \mathbb{E}. Projecting high-dimensional drawings onto two or three dimensions often results in drawings that are "smoother" and more symmetric. Among the other notable features of our approach are the utilization of a maximal independent set filtration of the set of vertices of a graph, a fast energy function minimization strategy, efficient memory management, and an intelligent initial placement of vertices. 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 mid-range PC.

Item Type:	Conference Paper
Classifications:	M Methods > M.999 Others M Methods > M.400 Force-directed / Energy-based P Styles > P.999 Others G Algorithms and Complexity > G.490 Embeddings P Styles > P.060 3D
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/363

Actions (login required)

View Item