Premium
The rotational dimension of a graph
Author(s) -
Göring Frank,
Helmberg Christoph,
Wappler Markus
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20502
Subject(s) - mathematics , combinatorics , dimension (graph theory) , bounded function , eigenvalues and eigenvectors , graph , monotone polygon , embedding , mathematical analysis , geometry , physics , quantum mechanics , artificial intelligence , computer science
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