University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Graduation Talks


Theory and applications of the graph Laplacian


Daniel Fleischer, University Konstanz
Konstanz, Germany

date & place

Wednesday, 24.01.2007, 15:15 h
Room C252


Various matrices are naturally associated with a graph, such as the adjacency matrix, the incidence matrix, and the Laplacian, all of which enable a fruitful interchange between (graph-theoretic) properties of a graph and algebraic properties of an associated matrix. E.g. the number of connected components of an undirected graph equals the dimension of the kernel of the Laplacian matrix. This thesis concentrates on the Laplacian matrix that can be seen as a discrete version of the Laplacian operator for the continuous case. This view implies discrete analogies to e.g. the Dirichlet problem and the integration theorems of Gauß and Stokes. In this talk the main focus will be on three new applications of the Laplacian matrix. The first one belongs to the domain of network analysis, where the matrix is used for the computation of electrical currents; the second application is graph drawing, where the matrix can be associated with a certain quadratic form that expresses a desired property of the drawing; finally, the Laplacian matrix is used to define a set of routing rules for sensor networks that guarantees message delivery, and generates short routes in practice.