Spectral Graph Drawing: A Survey

Graph Drawing is the science of finding an intuitive visualization of a network (or in mathematical terms of a graph). One approach is to define energy functions that represent design criteria for graph layouts. It happens to be that the eigenvalues of graph related matrices are locally optimal solutions for some of the energy functions. Using the eigenvalues for a graph layout is called Spectral Graph Drawing.This book is a survey of Spectral Graph Drawing methods. Graph layouts of several graph-related matrices, such as the adjacency or the Laplace matrix, are studied. There is a special section on the implementation of the graph layouts using the power iteration. At the end the focus is extended to the special requirements for Dynamic Spectral Graph Drawing, i.e. time-variant graphs are drawn with spectral methods. Zusammenfassung......Page 6 Introduction......Page 8 Graph Theory......Page 10 Basic Definitions......Page 11 Eigentheory......Page 13 Real Symmetric Matrices......Page 14 The Generalized Eigenvalue Problem......Page 17 Gershgorin's Discs and Extensions......Page 20 Perturbation Theory......Page 22 Adjacency Matrix......Page 26 Degree Matrix......Page 27 Laplace Matrix......Page 29 Relaxed Laplace Matrix......Page 31 Generalized Laplace Matrix......Page 35 Normalized Laplace Matrix......Page 37 Isomorphisms......Page 39 Eigenvalue Bounds......Page 40 Bounds of the Relaxed Laplace Matrix......Page 41 Bounds of the Generalized Laplace Matrix......Page 47 Motivation......Page 50 Laplace Layout......Page 53 Relaxed Laplace Layout......Page 57 Generalized Laplace Layout......Page 64 A Spectral Layout Algorithm......Page 68 Convergence Anormalities......Page 78 Dynamic Graph Drawing Using Spectral Layouts......Page 85 Conclusion......Page 91 Content of the Enclosed CD......Page 93