Like the adjacency, incidence matrix and other matrices associated with graphs, the Laplacian matrix enables a fruitful interplay between graph theory and linear algebra, where graph-theoretic properties of a graph are reflected by algebraic properties of one of its matrices.
Part 1, Chapters 1 and 2, considers well-known applications of the Laplacian matrix and compares the discrete and the continuous case, where in the latter case the Laplacian operator plays the role of the Laplacian matrix. Here we focus on two partial differential equations: wave and potential equation. Many properties and concepts like, e.g., the Dirichlet problem, meanvalue property, maximum principle, fundamental solutions, Perron's method, Dirichlet's principle, spectra, etc., exist both in the discrete and continuous case. Part 1 introduces the theoretical foundations for the applications of the second Part.
Part 2, Chapters 3 to 6, presents four new applications involving the Laplacian matrix:
The first application is from the area of network analysis. Two common measures for vertices of a graph are called closeness and betweenness for which exist two variants current-flow closeness and current-flow betweenness that consider the graph as an electrical network. By means of concepts from Part 1 these can be computed faster and can be well approximated.
Another application is (dynamic) graph drawing. Minimizing the sum of squared edge lengths corresponds to minimizing the energy of the graph. This is often used as a quality criterion for graph drawings. Its minimization can be done by a spectral decomposition of the Laplacian matrix. For dynamic graphs it is reasonable to use corresponding eigenvectors of linearly interpolated matrices. These can be computed efficiently and in particular for the random graph model small worlds their dynamics can be proven to be sufficiently smooth.
A third application is geographic routing in wireless networks. In a network of, say, small mini computers (vertices) with geographic positions in the plane, messages between arbitrary vertices should be sent. By means of the Laplacian matrix we can compute virtual positions. On these positions a simple set of routing rules guarantees message delivery and generates very short routes in practice.
Finally, the Laplacian matrix has an application in coloring graphs or data that basically corresponds to a graph. Anyhow, we do not consider the usual combinatorial optimization problem, but instead focus on the two objectives that adjacent vertices should be colored as different as possible, and the used colors can be distinguished well. This translates to a graph drawing problem into a color space with the unusual objective that edges should be as long as possible, while non-adjacent vertices should not be too close to each other.
Chapter 7 concludes with a brief summary, how concepts of the theory Part 1 entered the application Part 2.

Ebenso wie Adjazenz- und Inzidenzmatrix, die sich zu einem gegebenem Graphen definieren lassen, ermöglicht die Laplace-Matrix ein fruchtbares Zusammenspiel zwischen Graphentheorie und linearer Algebra. Viele Eigenschaften des Graphen spiegeln sich in algebraischen Eigenschaften der Matrizen wider.
In Teil 1 der Arbeit, Kapitel 1 und 2, betrachten wir bekannte Anwendungen der Laplace-Matrix und vergleichen zwischen diskretem und kontinuierlichem Fall, wobei in letzterem der Laplace-Operator die Rolle der Laplace-Matrix einnimmt. Hier stehen die beiden partiellen Differentialgleichungen Wellen- und Potenzialgleichung im Mittelpunkt. Viele bekannte Prinzipien aus der Potenzialtheorie lassen sich im diskreten und im kontinuierlichen Fall anwenden, wie etwa das Dirichlet-Problem, Mittelwerteigenschaft, Maximumprinzip, Grundlösungen, Methode von Perron, Dirichletsche Prinzip, Spektra, etc. Teil 1 liefert damit die theoretischen Grundlagen für die Anwendungen des zweiten Teils.
In Teil 2, Kapitel 3 bis 6, betrachten wir vier neue Anwendungen, welche die Laplace-Matrix verwenden:
Die erste Anwendung stammt aus dem Bereich der Netzwerkanalyse. Zwei bekannte Maße für Knoten eines Graphen sind closeness und betweenness. Zu diesen lassen sich Varianten current-flow closeness und current-flow betweenness definieren, die den Graphen als ein elektrisches Netzwerk auffassen. Mit Hilfe von Prinzipien aus Teil 1 lassen sich diese Varianten schneller berechnen und gut approximieren.
Eine weitere Anwendung ist das (dynamische) Zeichnen von Graphen. Die Minimierung der Summe der quadrierten Kantenlängen entspricht dem Minimieren der Energie des Graphen. Dies wird oft als ein Qualitätskriterium zum Zeichnen von Graphen verwendet. Die Minimierung kann durch Berechnen von Eigenvektoren der Laplace-Matrix gelöst werden. Für dynamische Graphen ist es sinnvoll, die entsprechenden Eigenvektoren von linear interpolierten Matrizen zu verwenden. Diese können effizient berechnet werden und ändern sich speziell für das Graphenmodell small worlds über die Zeit hinreichend glatt.
Eine dritte Anwendung ist geographic routing in drahtlosen Netzwerken. Hier sollen in einem Netzwerk von z.B. Minicomputern (Knoten) mit geographischen Positionen in der Ebene Nachrichten zwischen beliebigen Knoten verschickt werden. Mit Hilfe der Laplace-Matrix lassen sich (iterativ und verteilt) virtuelle Positionen berechnen, auf denen sich dann sehr einfache Regeln zum Weiterleiten von Nachrichten angeben lassen, die garantieren, dass Nachrichten ihr Ziel erreichen und in der Praxis sehr kurze Wege liefern.
Zuletzt lässt sich die Laplace-Matrix auch dazu verwenden, um Graphen zu färben bzw. Strukturen, aus denen sich leicht ein Graph ableiten lässt. Wir betrachten hier jedoch nicht das bekannte kombinatorische Optimierungsproblem, sondern konzentrieren uns auf die beiden Forderungen, benachbarte Knoten so unterschiedlich wie möglich zu färben und paarweise gut unterscheidbare Farben zu verwenden. Dieses Problem lässt sich als Graphenzeichnen-Problem in einen Farbraum auffassen. Im Vergleich zu sonst üblichen Qualitätskriterien verlangen die beiden Forderungen hier aber, dass Kanten möglichst lang sind, und dass alle Knoten paarweise einen gewissen Mindestabstand von einander haben.
Kapitel 7 schließt mit einer kurzen Zusammenfassung ab, wie die beiden Teile der Arbeit, Theorie und Anwendungen, miteinander verknüpft sind.