[Information Index] [Generation Index] [COS homepage]

Information on Chord Diagrams

A chord diagram is a set of 2n points on an oriented circle joined pairwise by n chords. Two chord diagrams are isomorphic if one can be obtained by some rotation of the other. The figure below illustrates all chord diagrams with three chords. In this figure and the ones to follow the circle is oriented in a counter-clockwise direction The algorithm generates the chord diagrams in the same order as shown in the diagram.

Representation

COS offers two representations for chord diagrams: a coloured bead representation and a string representation based on the distances between endpoints of the chords. Below we show the output of COS for n = 3. The listing corresponds to the list above.

Standard
Representation
Colored Beads
1 5 1 5 1 5
1 5 3 1 5 3
1 5 2 2 4 4
2 3 4 2 3 4
3 3 3 3 3 3

Bead Representation

First, assign each chord a unique value from 1 to n and then label the endpoints with the value of their incident chord. If we arbitrarily pick a starting point s, then we obtain a string representation by recording the endpoint values starting at s and moving counterclockwise (by convention) around the circle. In the example above the starting point is the topmost (red) bead. Any string with length 2n containing exactly two occurrences of the values 1 through n can be used to represent a chord diagram. An example of this string representation is shown in part A of the figure below. We consider such string representations with equivalence under string rotation and permutation of the alphabet symbols 1 through n. Thus, there may be up to 2n(n!) strings in each equivalence class, but there may be fewer. The lexicographically smallest strings in each equivalence class are more commonly known as unlabeled necklaces (where the number of each alphabet symbol is 2). To achieve a coloured bead representation, each symbol in the alphabet is represented by a different colour, with 1 = red, 2 = blue, 3 = green, etc.

   

String Representation by Length (Sawada representation)

Here we label each bead by the number k, where a rotation of 2 PI / k maps a bead to its mate under a counter clockwise rotation. Thus the sum of the labels of two like colored beads is always 2n. If we again traverse counterclockwise around the circle starting at s, recording the endpoint labels, we obtain a new string representation. As representative string we take the lexicographically smallest. An example of this string representation is given in part (b) of the figure above.

Other Information

For n = 1,2,3,...,22 the number of chord diagrams is 1, 2, 5, 18, 105, 902, 9749, 127072, 1915951, 32743182, 624999093, 13176573910, 304072048265, 7623505722157, 206342800616597, 127196366, 745028776, 4548125572, 28306102842, 182421784662, 1198160328838. This is sequence A007769 in Neil J. Sloane's database of integer sequences.

The algorithm used to generate chord diagrams is from the paper: Joe Sawada, A fast algorithm for generating nonisomorphic chord diagrams, SIAM J. Discrete Math, Vol. 15, No. 4, 2002, pp. 546-561.


Programs available:


[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 5378 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.