Paper Info
Title
The rotational dimension of a graph
Abstract
Given a connected graph G = (N, E) with node weights s∈ℝ **image** 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 vi∈ℝ|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 **image** 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 © 2011 Wiley Periodicals, Inc.
Year
DOI
Venue
2011
10.1002/jgt.20502
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
edge length,wiley periodicals,minor monotone graph parameter,eigenvalue optimization problem,inc. j graph theory,connected graph,following embedding problem,minimal dimension k,rotational dimension,minor characterization,tree width,graph partitioning,embedding,semidefinite programming,spectral graph theory
Discrete mathematics,Combinatorics,Line graph,Graph power,Dimension (graph theory),Graph embedding,Algebraic connectivity,Graph minor,Mathematics,Planar graph,Complement graph
Journal
Volume
Issue
ISSN
66
4
Electronic Notes in Discrete Mathematics
Citations 
PageRank 
References 
3
0.41
6
Authors
3
Name
Order
Citations
PageRank
Frank Göring1539.00
Christoph Helmberg252563.91
Markus Wappler3192.84