The rotational dimension of a graph

Given a connected graph G = ( N, E ) with node weights s ∈ℝ   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 ∈ℝ | N | , i ∈ N so that distances between adjacent nodes do not exceed prescribed edge lengths, the weighted barycenter of all points is at the origin, and 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 ℝ 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. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:283‐302, 2011