Fast Graph Drawing Using Sampled Spectral Distance

We present a fast spectral graph drawing algorithm for drawing undirected connected graphs. Classical Multi-Dimensional Scaling yields a quadratic-time spectral algorithm, which approximates the real distances of the nodes in the nal drawing with their graph theoretical distances. We build from this idea to develop the linear-time spectral graph drawing algorithm SSDE. We reduce the space and time complexity of the spectral decomposition by approximating the distance matrix with the product of three smaller matrices, which are formed by sampling rows and columns of the distance matrix. The main

advantages of our algorithm are that it is very fast and it gives aesthetically pleasing results, when compared to other spectral graph drawing algorithms. The runtime for typical 105 node graphs is about one second and for 106 node graphs about ten seconds. 1 Introduction A graph G = (V,E) is a pair where V is the vertex set and E is the edge set, which is a binary relation over V . The graph drawing problem is to compute an aesthetically pleasing layout of vertices and edges so that it is easy to grasp visually the inherent structure of the graph. In this paper, we only consider straight-line edge drawings for which a variety of aesthetic criteria have been studied: number of edge crossings; uniform node densities; symmetry. Depending on the aesthetic criteria of interest, various approaches have been developed, and a general survey can be found in [13,22]. For straight-line edge drawings, the graph drawing problem reduces to the problem of finding the coordinates of the vertices in two dimensions. A popular approach is to define an energy function or a force-directed model with respect to vertex positions, and to iteratively compute a local minimum of the energy function. The positions of the vertices at the local minimum produce the final layout. This approach is generally simple and easy to extend to new energy functions. Various energy functions and force models have been studied (see for example [6,12]) and there exist several improvements to handle large graphs, most of them concentrating on a multi-scale paradigm. Multi-scale approaches involve laying out a coarser level of the graph first, and then taking advantage of this coarse layout to compute the vertex positions at a finer level (see for example [9,24]). Spectral graph drawing was first proposed by Hall in 1970 [8] and it has be- come popular recently. We use the term spectral graph drawing to refer to any approach that produces a final layout using the spectral decomposition of some matrix derived from the vertex and edge sets of the graph. A general introduction can be found in [14]. In this paper, we present the spectral graph drawing algorithm SSDE (Sampled Spectral Distance Embedding), using a similar formulation that was introduced in [5], which uses Classical Multi-Dimensional Scaling (CMDS) techniques for graph drawing. CMDS for graph drawing was first introduced in [17] and recently, a similar...

Website: www.meliksah.edu.tr | Filesize: -
No of Page(s): 13
Download SSDE: Fast Graph Drawing Using Sampled Spectral Distance ....pdf