Can we uniquely define a graph to have the topology of a polytope via proper edge length selection? - MathOverflow

Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?

2010-11-24T02:32:07Z

I'll ask you to consider a situation wherein one has a series of edges for a graph, $(e_1, e_2, ..., e_N) \in E$, each with a specifiable length $(l_1, l_2, ..., l_N) \in L$, and the goal is to insure that the connected graph has a unique topology in 3-space. More specifically, I'm interested in insuring that some graph with the connectivity of a polytope can only be drawn as the skeleton of that particular polytope - that there should be no crossed edges or knots possible for the specified edge lengths.

To provide a physical example:

I use a group of rods to represent the edges of the desired graph (with pencils or the like) and color/symbol-encode their ends to represent vertex-assignments. I want to choose rod lengths in such a way that if I hand them to a naive-constructor (i.e. a 3-year old or a computer-controlled robot), and tell him/her/it to connect the ends of the rods together that have the same color or symbol, after waiting an arbitrarily long time there will only be a unique geometry satisfying the connectivity constraints of the graph I originally had in mind.

Is there a known computational complexity for this problem? Is there even a solution in the general case, or in the case where we apply the restriction that the specified polytope is convex?

I appreciate any feedback!

EDIT 1: The edges of the graph must be straight lines in 3-space, they cannot be bent to accommodate a particular edge length.

EDIT 2: Does the problem become easier if one assumes some physical diameter for the edges?

Answer by sleepless in beantown for Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?

2010-11-26T21:45:52Z

You are asking about the embedding of a graph structure into 3-space $\mathbb{R}^3$. A graph structure by itself does not specify its embedding into $n$-space. In chemistry, these two different chiral instances of (tetrahedral) molecules below would be called stereo-isomers or enantiomers of each other.

In mechanical engineering, you'd be talking about building trusses and support structures, and a lot is known about the fact that quadrilaterals do not define a rigid structure. Quadrilaterals are easily sheared within a plane, and are not restricted to being coplanar, whereas triangular faces are at least limited to being coplanar.

Also, the presence of these constraints (on edge length and vertex-edge connectivity) also does not mean that it would be impossible to build partial structures that meet the specified partial constraints but which cannot be built upon to complete the structure. In other words, a "naive constructor" cold generate a partial assembly which is a configuration which is impossible to continue onto a final desired construction. There could be dead-end partial constructions which could not be completed. This type of problem could partially be avoided by also imposing a temporal constraint, or a sequence constraint, e.g. first add this, then add that.

However, there are chirality issues in play which cannot be avoided.

If the "vertices" do not impose restrictions on relative angles, then there are no additional contraints beyond edge-length, and the graph-structure and edge lengths will not usually define a single embedding in 3-space, relative to transformations such as translation and rotation.

If by topology, you do not also mean chirality, you may be correct. If you allow chirality differences to mean something, then there is a simple counterexample in the tetrahedron.

Let this tetrahedron $T_1$ in $\mathbb{R}^3$ be defined with a base triangle $ABC$ with the points $A=(0,0,0), B=(0,1,0), C=(1,0,0)$ and the top of the tetrahedron at $D=(0,0,1)$. Let the edge lengths of the skeleton of this polytope be defined based on this baseline instantiation in 3-space, $|AB|=1, |AC|=1, |BC|=\sqrt{2}, |AD|=1, |BD|=\sqrt{2}, |CD|=\sqrt{2}$.

Now note that if $D$ is instead placed at $D_2=(0,0,-1)$, that the this alternate tetrahedron (let's call it $T_2=ABCD_2$), has the same edge lengths as $T_1$, but has the mirror chirality. If we labeled the vertices with $A,B,C,D$, it is not possible to rotate and translate $T_1$ into $T_2$, whereas it is possible to turn $T_1$ inside-out and transform it into $T_2$.

If you don't have all triangular faces, e.g. you use the edge lengths of a cube as the only constraints on a skeleton of a cube, you'll quickly see the problem that engineers found in constructing trusses with square faces: parallelograms are not necessarily "rigid" and can be sheared easily and still maintain the correct edge-lengths between vertices. Thus it's not possible to build a rigid skelton with only square faces.

Thus, it depends on the axiomatic construction of your objects:

if you disallow disassembly and reconstruction, then the tetrahedra $T_1$ and $T_2$ are separate chiral mirror-images of each other. If you allow for disassembly and reconstruction, then $T_1$ and $T_2$ have the same topology. If you also define "topologically equivalent" to allow for elastic stretching (at least for transforming from one 3-d realization to another, then back to being solid and rigid while in a specific 3-d realization), then $T_1$ can be transformed into $T_2$ by pushing the vertex $D$ through the center of the face $ABC$ and onto the other side. If the faces actually have a physical planar object defining that face (like a kite has its tissue paper), then this sort of transform is disallowed and the mirror image tetrahedra $T_1$ and $T_2$ are different.

You can also visualize this by allowing the edges to be made of elastic springy rods with spring constants $k_i$. If the $k$'s are very large, then the springs are very stiff and the inversion will be impossible; if the $k$'s are small, the springs have a lot of give and it's easily possible to change between the two mirror-image configurations.

Answer by jc for Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?

2010-11-26T22:52:56Z

This seems like a question in rigidity theory. In particular it seems like part of what you want is conditions for global rigidity in 3 dimensions.

Let me write down some definitions and basic facts from the introduction of this nice set of slides by Dylan Thurston and then post some references that might be helpful.

A framework is a graph and a map from its vertices into $d$-dimensional Euclidean space $\mathbb{E}^d$. A framework is locally rigid if every other framework in a small neighborhood with the same edge lengths is related to it by an isometry of $\mathbb{E}^d$. A framework is globally rigid if every other framework in $\mathbb{E}^d$ with the same edge lengths is related to it by an isometry of $\mathbb{E}^d$.

It turns out that checking global rigidity is NP hard, even in 1 dimension (Saxe 1979). However, if you're just interested in "generic" frameworks, i.e. those for which the edge lengths do not satisfy any polynomial relation, then work of Connelly and S. Gortler, A. Healy and D. Thurston characterizes these frameworks in any dimension with an efficient randomized algorithm. See the paper of GHT or the slides above. I must admit that I have not yet studied their work in any detail.

Since you are requiring that your frameworks are skeleta of polytopes, there may be extra structure which you can exploit. Let me just point you to Cauchy's rigidity theorem which states that convex polyhedra are rigid if you force the faces to be rigid in addition to the edges. If you don't have this restriction on the faces, then there are nonrigid examples, e.g. the 1-skeleton of a cube can be sheared, also pointed out in sleepless in beantown's answer. If you do have the restriction on the faces, but you allow nonconvex polyhedra, then there are flexible polyhedra.

In addition to the links above, there are several surveys on the webpage of Robert Connelly on various topics in rigidity theory.

Answer by Roland Bacher for Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?

2011-05-31T18:14:09Z

A matrix realizing Colin de Verdi`eres $\mu$-invariant yields an answer if you accept that you get lengths at the end, not at the beginning.

A planar graph $G$ arising as the $1-$skeleton of a polytope has always $\mu$-invariant equal to $3$. There exists thus a combinatorial Schr\"odinger operator on $G$ whose second largest eigenvalue has multiplicity $3$ (and the eigenspace satisfies a stability condition). Choose a basis of $3$ eigenvectors for such an operator. Interpret these eigenvectors as $x,y$ and $z$ coordinates of points in $\mathbb R^3$, indexed by vertices of $G$. This yields a set of points in $\mathbb R^3$ which are extremal vertices of a polytope realizing $G$ (and the realization is of course the obvious one, vertices are already labeled by vertices of $G$).

Moreover, all convex polytopes realizing $G$ can be constructed in this way. The "moduli space" of such polytopes is thus (up to the choice of a basis) in bijection with Schr\"odinger operators realizing the $\mu$ invariant.