On Spectral Graph Drawing

The spectral approach for graph visualization computes the layout of a graph using certain eigenvec- tors of related matrices. Some important advantages of this approach are an ability to compute optimal layouts (according to specific requirements) and a very rapid computation time. Here we explore vari- ous spectral visualization techniques and study their properties. We present a novel view of the spectral approach, which provides a direct link between eigenvectors and the aesthetic properties of the layout. In addition, we present a new formulation of the spectral drawing method with some aesthetic advan- tages. This formulation is accompanied

by an aesthetically-motivated algorithm, which is much easier to understand and to implement than the standard numerical algorithms for computing eigenvectors. 1 Introduction A graph G(V,E) is an abstract structure that is used to model a relation E over a set V of entities. Graph drawing is a standard means for visualizing relational information, and its ultimate usefulness depends on the readability of the resulting layout, that is, the drawing algorithm’s ability to convey the meaning of the diagram quickly and clearly. To date, many approaches to graph drawing have been developed [1, 10]. There are many kinds of graph-drawing problems, such as drawing di-graphs, drawing planar graphs and others. Here we investigate the problem of drawing undirected graphs with straight-line edges. In fact, the methods that we utilize are not limited to traditional graph drawing and are also intended for general low dimensional visualization of a set of objects according to their pair-wise similarities (see, e.g., Fig. 1). We have focused on spectral graph drawing methods, which construct the layout using eigenvectors of certain matrices associated with the graph. This approach is quite old, originating with the work of Hall [5] in 1970. However, since then it has not been used much. In fact, spectral graph drawing algorithms are almost absent in the graph-drawing literature (e.g., they are not mentioned in the two books [1, 10] that deal with graph drawing). It seems that in most visualization research the spectral approach is difficult to grasp in terms of aesthetics. Moreover, the numerical algorithms for computing the eigenvectors do not possess an intuitive aesthetic interpretation. We believe that the spectral approach has two distinct advantages that make it very attractive. First, it provides us with an exact solution to the layout problem, whereas almost all other formulations result in an NP-hard problem, which can only be approximated. The second advantage is computation speed. Spectral drawings can be computed extremely fast as we will show (for example, 10 5 nodes can be drawn in about a second). This is very important because the amount of information to be visualized is constantly growing exponentially. Spectral methods have become standard techniques in algebraic graph theory. The most widely used techniques utilize eigenvalues and eigenvectors of the adjacency matrix of the graph. More recently, the interest has shifted somewhat to the spectrum of the closely related Laplacian. In fact, Mohar [9] claims that the...

Website: reference.kfupm.edu.sa | Filesize: -
No of Page(s): 10
Download On Spectral Graph Drawing - CiteSeer.pdf