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.
Citation
Preprint 2008-16, Fakultät für Mathematik, Technische Universität Chemnitz, Germany, October 2008.