- The Rotational Dimension of a Graph Frank Göring(frank.goeringmathematik.tu-chemnitz.de) Christoph Helmberg(helmbergmathematik.tu-chemnitz.de) Markus Wappler(markus.wapplermathematik.tu-chemnitz.de) 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 Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 2: Combinatorial Optimization (Graphs and Matroids ) Citation: Preprint 2008-16, Fakultät für Mathematik, Technische Universität Chemnitz, Germany, October 2008. Download: [PDF]Entry Submitted: 10/30/2008Entry Accepted: 10/30/2008Entry Last Modified: 10/30/2008Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.