|
Published in:
A 2-dimensional framework (G,p) is a graph G=(V,E) together with a map p: V \to {\mathbb{R}}^2. We view (G,p) as a straight line realization of G in \mathbb{R}^2. Two realizations of G are equivalent if the corresponding edges in the two frameworks have the same length. A pair of vertices {u,v} is globally linked in G if the distance between the points corresponding to u and v is the same in all pairs of equivalent generic realizations of G. The graph G is globally rigid if all of its pairs of vertices are globally linked. We extend the characterization of globally rigid graphs given by the first two authors by characterizing globally linked pairs in M-connected graphs, an important family of rigid graphs. As a by product we simplify the proof of a result of Connelly which is a key step in the characterization of globally rigid graphs. We also determine the number of distinct realizations of an M-connected graph, each of which is equivalent to a given generic realization. Bounds on this number for minimally rigid graphs were obtained by Borcea and Streinu.
Bibtex entry:
| AUTHOR | = | {Jackson, Bill and Jord{\'a}n, Tibor and Szabadka, Zolt{\'a}n}, |
| TITLE | = | {Globally linked pairs of vertices in equivalent realizations of graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2005}, |
| NUMBER | = | {TR-2005-07} |