Spectral Graph Drawing

Introduction 1 15.2 Basic Notions ................................................. 3 Mathematical preliminaries 15.3 Spectral Graph Drawing .................................... 7 Energy-based Derivation of the Eigen-projection Method 15.4 Drawing using Degree-Normalized Eigenvectors ......... 9 15.5 A Direct Characterization of Spectral Layouts .......... 11 15.6 An Optimization Process.................................... 13 15.7 Spectral Drawings within a Subspace ..................... 14 The high dimensional embedding subspace • Eigen-projection in a subspace • Results of subspace-constrained optimization 15.8 Discussion ..................................................... 20 The spectral approach for graph visualization computes the layout of a graph using certain eigenvectors of related matrices. Some important advantages of this approach are an ability to compute

optimal layouts (according to specific requirements) and a very rapid compu- tation time. In this paper we explore spectral visualization techniques and study their properties from different points of view. We also suggest a novel algorithm for calculating spectral layouts resulting in an extremely fast computation by optimizing the layout within a small vector space. 15.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 [2, 3]. 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 pairwise similarities (see, e.g., Fig. 15.4). We have focused on spectral graph drawing methods, which construct the layout using eigenvectors of certain matrices associated with the graph. To get some feeling, we provide results for three graphs in Fig. 15.1. This spectral approach is quite old, originating with the work of Hall [4] 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 0-8493-8597-0/01/$0.00+$1.50 c© 2004 by CRC Press, LLC 1 2 CHAPTER 15. SPECTRAL GRAPH DRAWING (e.g., they are not mentioned in the two books [2, 3] 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 a mathematically-sound formulation leading into 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 show in Sec. 15.7. This is very important because the amount...

Website: www.cs.brown.edu | Filesize: -
No of Page(s): 24
Download Spectral Graph Drawing - Brown University.pdf