A Fast Multi-Dimensional Algorithm for Drawing

A Fast Multi-Dimensional Algorithm for Drawing Large Graphs∗ Pawel Gajer† Michael T. Goodrich‡ Stephen G. Kobourov§ Abstract We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space BX 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 BX. 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. 1 Introduction Graphs are common in many applications, from data structures to networks, from software engineering to databases. Typically, small graphsaredrawnmanuallyso that the resulting picture best showsthe underlying relationships. The task of drawing graphs by hand becomes more challenging as the complexity of the graphs increases. Graph drawing tools have been the focus of the graph drawing community for at least the last two decades, see [9, 10, 23] for a comprehensive reviews of the field. Numerous algorithms have been developed for drawing special classes of graphs such as trees and planar graphs. There are fewer general purpose graph drawing algorithms, however. Force-directed methods are the methods of choice for drawing general graphs. Substantial interest in force-directed methods stems from their conceptual simplicity, applicability to general graphs, and aesthetically pleasing drawings. With few exceptions, most existing automated systems have trouble dealing with graphs of thousands of vertices. In this paper we present a new algorithm which allows for drawing simple undirected graphs with tens of thousands of vertices in under a minute. Even larger graphs can be displayed using this algorithm in conjunction with a fisheye view [20, 28, 36] or multi-level display algorithm [11, 29] which would allow us to accomodate graphs with more vertices than the number of pixels of the display device. However, the effectiveness of the above algorithms depends on a good recursive clustering, which in turn depends on a good initial embedding of the graph. Creating a good embedding for large graphs has been prohibitively expensive using existing algorithms. Our algorithm allows us to create excellent initial embeddings in very reasonable times. The key features of the algorithm are: • intelligent initial placement of vertices • multi-dimensional drawing • a simple recursive coarsening scheme • fast energy function minimization • space and time efficiency ∗This research partially supported by NSF under Grant CCR-9625289, and ARO under grant DAAH04-96-1-0013. †Department of Computer Science, Johns Hopkins University, Baltimore, MD 21218 ‡Department...

Website: reference.kfupm.edu.sa | Filesize: -
No of Page(s): 11
Download A Fast Multi-Dimensional Algorithm for Drawing ... - Science Reference.pdf