Göring, Frank ; Helmberg, Christoph ; Wappler, Markus : The Rotational Dimension of a Graph
- Author(s):
-
Göring, Frank
Helmberg, Christoph
Wappler, Markus
- Title:
- The Rotational Dimension of a Graph
- Electronic source:
-
application/pdf
- 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 ] - Abstract:
- 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.
- Keywords:
- spectral graph theory, semidefinite programming, eigenvalue optimization, embedding, graph partitioning, tree-width
- Language:
-
English
- Publication time:
- 10 / 2008
