A *chord diagram* is a set of 2*n* 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.

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 |

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 2*n* 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 2*n*(*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.

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
2*n*.
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.

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:

- Chord Diagrams: C program .

(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 5375 visitors to this page since May 16, 2000 .

©Frank Ruskey, 1995-2003.