most recent 30 from http://mathoverflow.net 2013-05-19T04:45:07Z http://mathoverflow.net/feeds/user/11048 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/47181/can-we-uniquely-define-a-graph-to-have-the-topology-of-a-polytope-via-proper-edge ShallowBlue 2010-11-24T02:32:07Z 2011-05-31T18:14:09Z

<p>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. </p> <p>To provide a physical example: </p> <p>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. </p> <p>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?</p> <p>I appreciate any feedback!</p> <p>EDIT 1: The edges of the graph must be straight lines in 3-space, they cannot be bent to accommodate a particular edge length. </p> <p>EDIT 2: Does the problem become easier if one assumes some physical diameter for the edges?</p>

http://mathoverflow.net/questions/47181/can-we-uniquely-define-a-graph-to-have-the-topology-of-a-polytope-via-proper-edge/47467#47467 ShallowBlue 2010-11-27T01:36:21Z 2010-11-27T01:36:21Z

&quot;...we just have solve for the positions of the vertices, and ask whether all the solutions are related by translations or rotations.&quot; Right, I'm interested in picking rod lengths so that there's a solution for positioning vertices such that it can be drawn in 3-space. I'd also like to show that such a solution (and perhaps its mirror image) has a unique topology, that all such solutions are interconvertible by translations or rotations.

http://mathoverflow.net/questions/47181/can-we-uniquely-define-a-graph-to-have-the-topology-of-a-polytope-via-proper-edge/47467#47467 ShallowBlue 2010-11-27T00:50:00Z 2010-11-27T00:50:00Z

If instead of global rigidity, we ask that the naive-constructor must create a complete graph with some desired topology, is the problem still NP-hard?

http://mathoverflow.net/questions/47181/can-we-uniquely-define-a-graph-to-have-the-topology-of-a-polytope-via-proper-edge ShallowBlue 2010-11-24T06:10:32Z 2010-11-24T06:10:32Z

I apologize... but I don't see how the convex case is clear-cut. It seems to me like like it could <i>potentially</i> be possible to fix the edge lengths and connectivity constraints for a skeleton graph for some convex polytope, then reconfigure the graph (we don't care how this happens) into a knotted configuration without violating those constraints.

http://mathoverflow.net/questions/47181/can-we-uniquely-define-a-graph-to-have-the-topology-of-a-polytope-via-proper-edge ShallowBlue 2010-11-24T06:03:45Z 2010-11-24T06:03:45Z

Dear Andrew, no, I'm referring to arbitrary polytopes. However, for the convex case, it's not clear to me that it's always true that you can't find an alternate topology for a graph provided some set of edge lengths.