User steven gortler - MathOverflow

Answer by Steven Gortler for When does the rigidity matrix of a graph have full row rank?

2013-05-08T19:56:01Z

Not sure how helpful this will be, but: when the graph in question is infinitesimally rigid, then the existence of an equilibrium stress corresponds to the graph being "not minimally rigid". Also, graphs that are generically minimally rigid are called isostatic.

Answer by Steven Gortler for Does there exist a 3-connected, chordal graph which is not globally rigid?

2012-10-08T15:21:31Z

Every such graph is generically globally rigid in $E^2$. A 3-connected chordal graph can be built by starting with a triangle and then sequentially attaching new vertices to at least 3 previous ones. See this paper for some explicit statements. This idea generalizes to any dimension.

In fact, any generic (or even general position) framework for such a graph will be universally rigid in $E^2$, ie. it has no equivalent and non-congruent frameworks in any dimension. Such a graph is called generically universally rigid in $E^2$. (Note that you need to be a bit careful with universal rigidity as there are graphs that have some generic frameworks that are universally rigid in $E^2$, and other generic frameworks that are not universally rigid in $E^2$.)

Answer by Steven Gortler for Why is this graph not generically globally rigid?

2012-01-25T18:36:26Z

The graph is generically globally flexible in the plane (see Joe's example). But even for such a graph, there can be special (non-generic) drawings that are globally rigid. Yours is one such drawing. Violations in this direction can only occur when the drawing itself becomes infinitesimally flexible (ie. its rigidity matrix drops its rank).

Answer by Steven Gortler for SDP Feasibility

2011-06-07T19:14:23Z

As already answered, the complexity of the SDP feasibility problem is unknown. Some interesting complexity results on this problem are contained in the following paper.

@article{ramana1997exact, title={An exact duality theory for semidefinite programming and its complexity implications}, author={Ramana, M.V.}, journal={Mathematical Programming}, volume={77}, number={1}, pages={129--162}, year={1997}, publisher={Springer} }

Answer by Steven Gortler for Is the following two-dimensional graph likely to be globally rigid?

2011-05-02T02:59:42Z

Note that condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.) Though, as Dylan just explained, when the graph is "dense" enough to be universally rigid, then there is an efficient algorithm for (approximate) localization.

Answer by Steven Gortler for Is the following two-dimensional graph likely to be globally rigid?

2011-05-02T02:51:46Z

(this should be a comment, but I have no such privileges)
@jc: You are correct, that, by genericity, all one is really trying to do, is avoid a few specific bad algebraic subsets. The main ones to avoid are places where the rigidity matrix, or the stress matrix has a "less than maximal rank". There is also one more bad subset that needs to be avoided: non-smooth points of the so-called "measurement set" where it self intersects. At such points, global rigidity can be lost. Avoiding such places is needed in Connelly's sufficiency proof. See Example 8.1 in Connelly and Whiteley's "Global Rigidity: The effect of coning" for an example where this subset is hit.

Comment by Steven Gortler

2013-05-08T19:50:15Z

The Maxwell-Cremona theorem is primarily concerned with planar graphs.