John Conway wrote:

the "Carpenter's Ruler" problem (are the plane embeddings of a hinged ruler interconvertible in this way, keeping the segment-lengths fixed) is quite difficult - [...] and the corresponding assertion for arbitary graphs is false.

Andy Latto wrote:

Is there an easy-to-describe counterexample?

It's false even with a single degree-3 vertex, i.e., 3 attached "rulers". See http://theory.lcs.mit.edu/~edemaine/papers/InfinitesimallyLocked_LasVegas/ for this example. A simpler (and older) example is in http://theory.lcs.mit.edu/~edemaine/papers/LockedTreeDAM/ Of course, these linkage problems are quite different from Dan's original question, which did not require edge lengths to stay fixed:

Still a mystery to me is this: Given a graph G embedded in the plane, under what circumstances can a straight-line version of G be obtained through a continuous deformation of the original embedding, through embeddings ?

I don't quite see the issue of continuous deformation here. (As I understand it, only the final embedding has to be straight-line.) Can't any two topologically equivalent embeddings (in the sense that the cyclic order around each vertex is identical in two embeddings) be obtained by continuous deformation? (Perhaps this is what you're asking.) If so, then Tutte's theorem on graph drawing proves the rest: W. T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, 13(52):743-768, 1963. I even wonder whether Tutte's construction (via springs & barycenters) might be adapted to give a continuous motion. This recent followup may be relevant: http://www.ehess.fr/centres/cams/person/pom/tutte-s-barycenter-method.ps Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/