Globally Rigid Circuits of the Direction-Length Rigidity Matroid

Bill Jackson, Tibor Jordán

Published in:
J. Combinatorial Theory, Ser. B., Vol. 100, 1-22, 2010.


A two-dimensional mixed framework is a pair (G,p), where G=(V;D,L) is a graph whose edges are labeled as `direction' or `length' edges, and p is a map from V to $R2. The label of an edge uv represents a direction or length constraint between p(u) and p(v). The framework (G,p) is called globally rigid if every framework (G,q) in which the direction or length between the endvertices of corresponding edges is the same as in (G,p), can be obtained from (G,p) by a translation and, possibly, a dilation by -1.

We characterize the generically globally rigid mixed frameworks (G,p) for which the edge set of G is a circuit in the associated direction-length rigidity matroid. We show that such a framework is globally rigid if and only if each 2-separation S of G is `direction balanced', i.e. each `side' of S contains a direction edge. Our result is based on a new inductive construction for the family of edge-labeled graphs which satisfy these hypotheses. We also settle a related open problem posed by Servatius and Whiteley concerning the inductive construction of circuits in the direction-length rigidity matroid.

Bibtex entry:

AUTHOR = {Jackson, Bill and Jord{\'a}n, Tibor},
TITLE = {Globally Rigid Circuits of the Direction-Length Rigidity Matroid},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2008},
NUMBER = {TR-2008-09}

Last modification: 29.12.2020. Please email your comments to Tamás Király!