# Detecting rotational symmetries of spatial structures

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.

• 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? – D.W. Aug 30 '19 at 22:34
• I only care about the entire graph, not the subgraphs. – Botond Sep 2 '19 at 0:18

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.