SDE: Graph drawing using spectral distance embedding

Abstract. 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 shortest 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.