On rigidity and realizability of weighted graphs

Submitted by R.A. Brualdi
https://doi.org/10.1016/S0024-3795(00)00281-0Get rights and content
Under an Elsevier user license
open archive

Abstract

Recently, a new characterization of rigid graphs was introduced using Euclidean distance matrices (EDMs) [A.Y. Alfakih, Linear Algebra Appl. 310 (2000) 149]. In this paper, we address the computational aspects of this characterization. Also we present a characterization of graphs which are realizable in Rr for some 1⩽r⩽n−2 but not realizable in R(n−1), where n is the number of nodes.

MSC

94C15
52A20
05C50
15A57

Keywords

Weighted graphs
Rigidity
Realizations of graphs
Euclidean distance matrices
Slater condition
Convex sets
Semidefinite programming

Cited by (0)

Supported by the Deutsche Forschungsgemeinschaft through the graduate program Angewandte Algorithmische Mathematik, Technische Universität München.

1

Present address: The Fields Institute, 222 College Street, Toronto, Ont., Canada M5T 3J1.