首页 | 本学科首页   官方微博 | 高级检索  
     


Graph rigidity via Euclidean distance matrices
Authors:AbdoY. Alfakih  
Affiliation:

DepartmentofCombinatoricsandOptimization,UniversityofWaterloo, Waterloo,Ont., Canada N2L 3G1

Abstract:Let G=(V,E,ω) be an incomplete graph with node set V, edge set E, and nonnegative weights ωij's on the edges. Let each edge (vi,vj) be viewed as a rigid bar, of length ωij, which can rotate freely around its end nodes. A realization of a graph G is an assignment of coordinates, in some Euclidean space, to each node of G. In this paper, we consider the problem of determining whether or not a given realization of a graph G is rigid. We show that each realization of G can be epresented as a point in a compact convex set ; and that a generic realization of G is rigid if and only if its corresponding point is a vertex of Ω, i.e., an extreme point with full-dimensional normal cone.
Keywords:Weighted graphs   Rigidity   Euclidean distance matrices   Convex sets   Normal cones   Semidefinite programming
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号