Theory and Applications of the Laplacian

Cite This

Files in this item

Checksum: MD5:a8b1df82f247b3a6333dd97df46b3c95

FLEISCHER, Daniel, 2007. Theory and Applications of the Laplacian [Dissertation]. Konstanz: University of Konstanz

@phdthesis{Fleischer2007Theor-5507, title={Theory and Applications of the Laplacian}, year={2007}, author={Fleischer, Daniel}, address={Konstanz}, school={Universität Konstanz} }

eng application/pdf terms-of-use 2007 2011-03-24T15:56:05Z Theorie und Anwendungen der Laplace-Matrix und des Laplace-Operators Fleischer, Daniel 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.<br />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.<br />Part 2, Chapters 3 to 6, presents four new applications involving the Laplacian matrix:<br />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.<br />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.<br />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.<br />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.<br />Chapter 7 concludes with a brief summary, how concepts of the theory Part 1 entered the application Part 2. 2011-03-24T15:56:05Z Fleischer, Daniel Theory and Applications of the Laplacian

Downloads since Oct 1, 2014 (Information about access statistics)

Fleischer_Diss.pdf 2823

This item appears in the following Collection(s)

Search KOPS


My Account