Graph rigidity via Euclidean distance matrices

Authors
Citation
Ay. Alfakih, Graph rigidity via Euclidean distance matrices, LIN ALG APP, 310(1-3), 2000, pp. 149-165
Citations number
24
Categorie Soggetti
Mathematics
Journal title
LINEAR ALGEBRA AND ITS APPLICATIONS
ISSN journal
00243795 → ACNP
Volume
310
Issue
1-3
Year of publication
2000
Pages
149 - 165
Database
ISI
SICI code
0024-3795(20000501)310:1-3<149:GRVEDM>2.0.ZU;2-F
Abstract
Let G = (V, E, omega) be an incomplete graph with node set V,edge set E, an d nonnegative weights wij 's on the edges. Let each edge (vi, vj) be viewed as a rigid bar, of length omega 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 nor a given realization of a graph G is rigid. W e show that each realization of G can be represented as a point in a compac t convex set Omega subset of R-(m) over bar; and that a generic realization of G is rigid if and only if its corresponding point is a vertex of Omega, i.e., an extreme point with full-dimensional normal cone. (C) 2000 Elsevie r Science Inc. All rights reserved.