The Rotational Dimension of a Graph

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