Optimization Online


The Rotational Dimension of a Graph

Frank Göring(frank.goering***at***mathematik.tu-chemnitz.de)
Christoph Helmberg(helmberg***at***mathematik.tu-chemnitz.de)
Markus Wappler(markus.wappler***at***mathematik.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society