I conjecture that the number of 'degrees of freedom' = the number of connected components of the undirected graph. Proof sketch. Consider any simple cyclic path in the graph & throw away the rest of the graph (for the moment). Each vertex in the path now has degree exactly 2. But the same 'angle bisector' argument for the triangle (see below) shows that once the angle choice is made for one of the struts incident on the vertex, the same choice is required for the other incident strut. By induction, the choice on one strut constrains the choice on every other strut in the cycle. We thus have at most one consistent labelling for the entire cycle. But can we always make a consistent choice for the entire cycle? Yes, because we can always _triangulate_ the cycle. I.e., if we start from a particular vertex in the cycle, this constrains both incident edges. But we can now shorten the cycle by one edge & one vertex by removing that vertex & both incident edges & installing a new edge between the opposite ends of the removed edges. Eventually, we produce a triangle, which we already know can be consistently labelled. Reversing the steps, we now know that the entire cycle is determined by the rotation of any single strut edge in the cycle. But this means that any one edge incident on the vertex constrains every other edge incident on that vertex, because we can always choose a path that includes both edges. Thus, the entire connected component has at most one degree of freedom, and at least one degree of freedom. It would be neat to _animate_ such an embedded graph by rotating the faces of all the struts in unison. (What kind of gear train would be required inside the vertices in order to achieve this unanimous rotation?) At 05:53 AM 6/4/2013, you wrote:
I've been hacking some code for building 'networks' in 3D out of 'nodes' and 'links'.
Here's the problem.
I have a very large undirected graph -- e.g., O(10^6) vertices/faces/edges -- that I want to embed in 3D.
I make an assignment of vertices to 3D points, and would then like to 'link' these points together with 'links'/'struts' which are right regular cylindrical polyhedra.
Thus, given points P1=[x1,y1,z1], P2=[x2,y2,z2], I want to 'link' P1 to P2 with a 'strut' whose cross section is a regular n-gon (e.g., equilateral triangle) of some fixed size (e.g., side length = 10 millimeters).
For the moment, I will completely ignore the problem of choosing the 3D locations of the vertices so that the struts do not interfere/intersect -- except where two (or more) struts meet at a vertex node. (This will be easy if I construct the graph embedding in the first place with no such interferences/intersections.)
We thus assume that we have a 'good' embedding of vertices/nodes in 3D such that the struts don't interfere/intersect except at the vertices/nodes themselves.
Note that when we have a 'strut' from P1 to P2, the line down the exact center of this strut goes exactly from P1 to P2.
However, the angles/faces where two such struts meet can be quite complex.
Thus, the only degree of freedom for the strut from P1 to P2 is the _rotation angle_ of the strut around the line from P1 to P2 as the axis of rotation.
I'd like to minimize the complexity (in terms of the number of faces/facets) of the overall structure, which means minimizing the number of faces where the struts come together at the vertices.
Consider one of the simplest examples: a complete graph of 3 vertices joined by 3 edges/links, which I embed in 3D as an equilateral triangle.
I want the links to have cross-sections which are regular n-gons -- e.g., triangles.
I could choose to have the 'flat' part of all three struts on the _outside_ of the big triangle linking the 3 nodes. Each pair of struts would meet at a 60 degree angle and generate no additional faces.
Or I could choose to have the 'edge' part of all three struts on the _ outside_ of the big triangle linking the 3 nodes. Each pair of struts would still meet at a 60 degree angle and generate no additional faces.
But I could choose _any angle_ for one strut around its long axis, and -- so long as I choose the _same angle_ for the other two struts -- I can still arrange for the struts to meet at the vertices/nodes with no additional faces.
I.e., the complete graph of 3 vertices and 3 edges has only 1 degree of freedom.
Q: what happens if the location assignment of the graph to 3D is no longer equilateral? Am I now forced to have additional faces?
A: No, we can still have simple joins. Proof: look at the 3 planes which are the angle bisectors of the embedded triangle. When 2 struts meet at such an angle bisector plane, they intersect the angle bisector plane at the same triangle if their rotation angle about their long axis is the same. Thus, _any_ embedded triangle still has exactly 1 degree of freedom: if we choose the rotation angle of any 1 of the 3 struts, the rotation angles of the other two struts are constrained to be the same.
Q: what happens with more complex objects -- e.g., what happens if I start with a _planar_ graph & use a location assignment that preserves its planarity. What exactly do the nodes look like where the struts come together at random angles?
Q: what happens with non-planar embeddings -- e.g., a graph that looks like a regular (or perhaps non-regular) tetrahedron?