I have a spatial graph-like structure. The structure consists of vertices in the 3D space and connecting edges. Are there any algorithms available that would identify the rotational symmetries of these structures? In particular, I'm interested in all the rotational axis along which I can rotate the structure to overlap itself, as well as the degree of rotation. For example, an equilateral triangle (3 vertices + 3 edges) would have one rotational axis perpendicular to its plane, with a degree of 3 and 3 others in its plane, with a degree of 2 each. The closest I could find are molecular packages identifying the symmetry groups of molecular structures. I would prefer not to go that far as I'm only interested in rotational symmetries and not entire group theory description of structures.

  • 3
    $\begingroup$ Do you want to check whether the entire graph is rotationally symmetric? Or do you want to identify whether there exists some subgraph that is rotationally symmetric? $\endgroup$ – D.W. Aug 30 '19 at 22:34
  • $\begingroup$ I only care about the entire graph, not the subgraphs. $\endgroup$ – Botond Sep 2 '19 at 0:18

Here is one approach to identify all rotational symmetries of the graph:

Pick any three vertices, $v_1,\dots,v_3$. Loop over all possible combinations of three vertices $w_1,\dots,w_3$. For each such combination, find the unique rotation that maps $v_1 \mapsto w_1,\dots,v_3 \mapsto w_3$, then check whether this is a rotational symmetry of the entire graph (by mapping the entire graph and seeing whether the mapped graph coincides with the original graph).

The worst-case running time will be something like $O(n^4)$, where $n$ is the number of vertices in the graph. In practice I expect it to be typically more like $O(n^3)$, as most candidate rotations can be immediately rejected by testing a few vertices.

To identify the unique rotation that maps $v_1 \mapsto w_1,\dots,v_3 \mapsto w_3$, given $v_1,\dots,v_3,w_1,\dots,w_3$, see https://math.stackexchange.com/q/3341635/14578.

  • $\begingroup$ Can you please elaborate on why you need to pick 5 vertices and not 3, 4, or 6? The question is then the same for the 5 vertices, like you said: how would one identify the unique rotations for those? $\endgroup$ – Botond Sep 2 '19 at 0:17
  • 1
    $\begingroup$ @Botond, see updated answer. $\endgroup$ – D.W. Sep 2 '19 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.