SDE: Graph Drawing Using Spectral Distance Embedding

We present a novel algorithm for drawing undirected connected graphs, by using a spectral decomposition of the distance matrix to approximate the graph theoretical distances. The main advantages of our algorithm are that it is ”exact” (as opposed to iterative), and it gives results that preserve symmetry and uniform node density, i.e., the drawings are aesthetically pleasing. Our approach has the benefits of fast spectral techniques, but at the same time it produces drawings of a quality comparable to or better than the much slower force-directed approaches. The

computational complexity of our algorithm is governed by its two main steps: distance matrix computation using an all-pairs short- est path algorithm, which is O(|V||E|); and low-order spectral decomposition, which is O(|V|2). The runtime for typical 20,000 node graphs ranges from 100 to 150 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. Depending on the aesthetic criteria of interest, various approaches have been developed, and a general survey can be found in [11,16]. We consider only the straight-line edge drawings of graphs, which reduces the problem to 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 [4–6, 10] and there exist several improvements to handle large graphs, most of them concentrating on a multi-scale paradigm. This involves 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 (eg. [15,18]). Spectral graph drawing approaches have become popular recently. We use the term spectral graph drawing to refer to any approachthat produces a final layout using the spectral decomposition of some matrix derived from the vertex and edge sets. In this paper, we present a spectral graph drawing algorithm, SDE (Spectral Distance Embedding), in which we use the spectral decomposition of the graph theoretical distance matrix to produce the final layout of the vertices. In the final layout, the pair-wise Euclidean distances of the vertices approximate the graph theoretical distances. SDE consists of two main steps: (i) all-pairs shortest path computation, which takes O(|V||E|) time. (ii) spectral decomposition of the distance matrix, in which we find the optimal rank-d reconstruction to embed in d-dimensions. The complexity of this step is O(d|V|2). SDE can be used to produce a d-dimensional...

Website: www.cs.rpi.edu | Filesize: -
No of Page(s): 12
Download SDE: Graph Drawing Using Spectral Distance Embedding.pdf