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/2008
Entry Accepted: 10/30/2008
Entry Last Modified: 10/30/2008

Modify/Update this entry