Springe zum Hauptinhalt
Fakultät für Mathematik
Fakultät für Mathematik
Göring, Frank; Helmberg, Christoph ; Wappler, Markus : The Rotational Dimension of a Graph

Göring, Frank ; Helmberg, Christoph ; Wappler, Markus : The Rotational Dimension of a Graph

Göring, Frank
Helmberg, Christoph
Wappler, Markus
The Rotational Dimension of a Graph
Electronic source:
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 16, 2008
Mathematics Subject Classification:
05C50 [ Graphs and matrices ]
90C22 [ Semidefinite programming ]
90C35 [ Programming involving graphs or networks ]
05C10 [ Topological graph theory, imbedding ]
05C78 [ Graph labelling ]
Given a connected graph $G=(N,E)$ with node weights $s\in\R^N_+$ and nonnegative edge lengths, we study the following embedding problem related to an eigenvalue optimization problem over the second smallest eigenvalue of the (scaled) Laplacian of $G$: Find $v_i\in\R^{|N|}$, $i\in N$ so that distances between adjacent nodes do not exceed prescribed edge lengths, the weighted barycenter of all points is at the origin, and $\sum_{i\in N}s_i\|v_i\|^2$ is maximized. In the case of a two dimensional optimal solution this corresponds to the equilibrium position of a quickly rotating net consisting of weighted mass points that are linked by massless cables of given lengths. We define the rotational dimension of $G$ to be the minimal dimension $k$ so that for all choices of lengths and weights an optimal solution can be found in $\R^k$ and show that this is a minor monotone graph parameter. We give forbidden minor characterizations up to rotational dimension 2 and prove that the rotational dimension is always bounded above by the tree-width of $G$ plus one.
spectral graph theory, semidefinite programming, eigenvalue optimization, embedding, graph partitioning, tree-width
Publication time:
10 / 2008