Return to search

On Graph Embeddings and a new Minor Monotone Graph Parameter associated with the Algebraic Connectivity of a Graph

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.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:ch1-qucosa-115518
Date07 June 2013
CreatorsWappler, Markus
ContributorsTU Chemnitz, Fakultät für Mathematik, Prof. Dr. Christoph Helmberg, Univ.-Prof. Dipl.-Ing. Dr. Franz Rendl
PublisherUniversitätsbibliothek Chemnitz
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:doctoralThesis
Formatapplication/pdf, text/plain, application/zip

Page generated in 0.0023 seconds