Spectral graph drawing

✍ Scribed by Thomas Puppe

• Publisher: VDM Verlag
• Year: 2008
• Tongue: English
• Leaves: 95
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Zusammenfassung......Page 5
Introduction......Page 7
Graph Theory......Page 9
Basic Definitions......Page 10
Eigentheory......Page 12
Real Symmetric Matrices......Page 13
The Generalized Eigenvalue Problem......Page 16
Gershgorin's Discs and Extensions......Page 19
Perturbation Theory......Page 21
Adjacency Matrix......Page 25
Degree Matrix......Page 26
Laplace Matrix......Page 28
Relaxed Laplace Matrix......Page 30
Generalized Laplace Matrix......Page 34
Normalized Laplace Matrix......Page 36
Isomorphisms......Page 38
Eigenvalue Bounds......Page 39
Bounds of the Relaxed Laplace Matrix......Page 40
Bounds of the Generalized Laplace Matrix......Page 46
Motivation......Page 49
Laplace Layout......Page 52
Relaxed Laplace Layout......Page 56
Generalized Laplace Layout......Page 63
A Spectral Layout Algorithm......Page 67
Convergence Anormalities......Page 77
Dynamic Graph Drawing Using Spectral Layouts......Page 84
Conclusion......Page 90
Content of the Enclosed CD......Page 92