We consider the problem of maximizing the second smallest eigenvalue of the weighted Laplacian of a (simple) graph over all nonnegative edge weightings with bounded total weight.
We generalize this problem by introducing node significances and edge lengths.
We give a formulation of this generalized problem as a semidefinite program.
The dual program can be equivalently written as embedding problem. This is fifinding an embedding of the n nodes of the graph in n-space so that their barycenter is at the origin, the distance between adjacent nodes is bounded by the respective edge length, and the embedded nodes are spread as much as possible. (The sum of the squared norms is maximized.)
We proof the following necessary condition for optimal embeddings. For any separator of the graph at least one of the components fulfills the following property: Each straight-line segment between the origin and an embedded node of the component intersects the convex hull of the embedded nodes of the separator.
There exists always an optimal embedding of the graph whose dimension is bounded by the tree-width of the graph plus one.
We defifine the rotational dimension of a graph. This is the minimal dimension k such that for all choices of the node significances and edge lengths an optimal embedding of the graph can be found in k-space.
The rotational dimension of a graph is a minor monotone graph parameter.
We characterize the graphs with rotational dimension up to two.:1 Introduction
1.1 Notations and Preliminaries
1.2 The Algebraic Connectivity
1.3 Two applications
1.4 Outline
2 The Embedding Problem
2.1 Semidefinite formulation
2.2 The dual as geometric embedding problem
2.3 Physical interpretation and examples
2.4 Formulation without fifixed barycenter
3 Geometrical Operations
3.1 Congruent transformations
3.2 Folding a flat halfspace
3.3 Folding and Collapsing
4 Structural properties of optimal embeddings
4.1 Separator-Shadow
4.2 Separators containing the origin
4.3 The tree-width bound
4.4 Application to trees
5 The Rotational Dimension of a graph
5.1 Defifinition and basic properties
5.2 Characterization of graphs with small rotational dimension
5.3 The Colin de Verdi ere graph parameter
List of Figures
Bibliography
Theses
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:19916 |
| Date | 30 May 2013 |
| Creators | Wappler, Markus |
| Contributors | Helmberg, Christoph, Rendl, Franz, Technische Universität Chemnitz |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0025 seconds