Find symmetries of a tree

Question

I have n sectors, enumerated 0 to n-1 counterclockwise. The boundaries between these sectors are infinite branches (n of them). The sectors live in the complex plane, and for n even, sector 0 and n/2 are bisected by the real axis, and the sectors are evenly spaced.

These branches meet at certain points, called junctions. Each junction is adjacent to a subset of the sectors (at least 3 of them).

Specifying the junctions, (in pre-fix order, lets say, starting from junction adjacent to sector 0 and 1), and the distance between the junctions, uniquely describes the tree.

Now, given such a representation, how can I see if it is symmetric wrt the real axis?

For example, n=6, the tree (0,1,5)(1,2,4,5)(2,3,4) have three junctions on the real line, so it is symmetric wrt the real axis. If the distances between (015) and (1245) is equal to distance from (1245) to (234), this is also symmetric wrt the imaginary axis.

The tree (0,1,5)(1,2,5)(2,4,5)(2,3,4) have 4 junctions, and this is never symmetric wrt either imaginary or real axis, but it has 180 degrees rotation symmetry if the distance between the first two and the last two junctions in the representation are equal.

Edit: Here are all trees with 6 branches, distances 1. http://www2.math.su.se/~per/files/allTrees.pdf

So, given the description/representation, I want to find some algorithm to decide if it is symmetric wrt real, imaginary, and rotation 180 degrees. The last example have 180 degree symmetry.

Edit 2: If all length of the distances between the junctions were all the same, it is quite easy to find the reflection/rotation of a tree. The problem arises when the distances are of unequal length.

Notice that if I have a regular n-gon, with some non-intersecting chords, is sort of the dual to my trees. I use this in the drawing algorithm, for those that wonder.

That is, I create the n roots of unity (possible with some rotation), then the angle between junction (123) and (345) would be the same as for the mean of vertices 1,2,3 to the mean of vertices 3,4,5 in this n-gon.

The angles in the drawing is not really important, you may change the angles, but the order of the long branches should be the same, and you cannot rotate the tree.

EDIT 3:

Observe that there are many ways of drawing the trees. What I have is an equivalence relation, T1 ~ T2 if the two trees have the same junction representation. If S is an axis symmetry, or rotation by 180 degrees, Then S(T1) ~ S(T2), so the notion of being the same tree is well-defined. The question is therefore, how to determine if S(T1) ~ T1, or even better, compute S(T1). By above, this is independent on how I draw the tree.

Answer 1

I don't understand how the angles of the connecting finite segments are determined, so I'll assume the angles are set so that they don't break any symmetry. First observe that the reflection wrt the real axis sends sectors 0,1,2,3,4,5 to 0,5,4,3,2,1 respectively. So in your second example, tree

(0,1,5)(1,2,5)(2,4,5)(2,3,4) turns into

(0,5,1)(5,4,1)(4,2,1)(4,3,2)

which is different from the original tree (the original and transformed tree share only the first and last junction). So the transformation is not a symmetry of the tree. However, the same transformation sends the first example

(0,1,5)(1,2,4,5)(2,3,4) to

(0,5,1)(5,4,2,1)(4,3,2)

which is the same tree, represented in a non standard way because the junctions appear in the wrong order and the sectors of each junction are also in the wrong order.

Rotation of 180 degrees sends 0,1,2,3,4,5 to 3,4,5,0,1,2 (add 3 mod 6) so

(0,1,5)(1,2,5)(2,4,5)(2,3,4) turns into

(3,4,2)(4,5,2)(5,1,2)(5,0,1)

which is the same tree, again represented in a non standard way (the junctions appear in the inverse order, and each junction has its inciding sectors cycled).

So the recipe seems to be the following: Find out, for your transformation of the plane, which sectors goes to which, apply this permutation to the tree representation, and then reorder each tree representation (original and transformed) in a standard way that allows to compare if they are equal. If they are equal, then (assuming the angles are nice), the transformation of the plane is a symmetry of the tree. If they are not equal, then the transformation is not a symmetry of the tree.

Answer 2

but the order of the long branches should be the same, and you cannot rotate the tree.

So 'order' has nothing to do with the geometrical length, right? It is the depth of the tree that you are talking about?

It seems that the identity of a junction is its angular order (0 <= j < n), its position in the tree (using some traversal), and the quadrant of the complex plain it inhabits. It seems like the quadrant is totally determined by the angular order (j in my diagram):

{ { (n/4 <= j < n/2) (-/+), (j < n/4) (+/+) }, { (n/2 <= j < 3n/4) (-/-) , (3n/4 < j < n) (+/-)} }