**Drawing Chords on a Disk**

Consider the regular *2n*-gon in the plane. We wish to draw *n*
paths, called *chords*, through the interior connecting antipodal points
on the polygon. Every pair of chords must intersect. We adopt the usual
conventions for drawing graphs:

1. no chord intersects itself,

2. two distinct chords intersect in at most one point, and

3. at most two chords intersect at any point.

Two drawings are *isomorphic* if there exists a homeomorphism of the
plane which fixes the *2n*-gon and carries one drawing onto another. For
example, there is a unique drawing of the square with two chords. Likewise,
there are exactly two distinct drawings of the hexagon with three chords. These
two drawings are identical under a reflection, but they are not isomorphic.

**Question:** *Find the number of nonisomorphic drawings of a *2n-*gon
with* n *pairwise crossing chords*.

Denote this number by *f(n)*. I can show that the sequence *f(n)*
begins 1, 1, 2, 8, 62, 908, 24698. The values for *n = 1,2* are obvious,
the values for *n = 3,4,5* can be verified by hand, and the values for *n
= 6,7* were calculated using a computer.

Ringel [R] showed that any one drawing can be transformed into any other by a sequence of Reidemeister moves of type iii and gives some related insights and motivation.

The *Mobius ladder* of order *2n*, *M_n*, is the 3-regular
graph with a Hamiltonian cycle (1,2,...,2n,1) and edges joining vertex *i*
to *i+n*, *i = 1,...,n*. The above problem is equivalent to finding
the number of drawings of *M_n* in a disk where the distinguished
Hamiltonian cycle maps homeomorphically to the boundary of the disk in a fixed
manner. We call this a *disk drawing* of *M_n*. We generalize the
preceding problem by asking for the number of disk drawings of an arbitrary
graph with a distinguished Hamiltonian cycle. Here we add the requirement that
two chords incident with a common vertex do not cross. By repeated vertex
splittings this reduces to the case where the graph is 3-regular.

Another variation on the problem would be to allow rotations and/or
reflections of the disk. I have also heard of finding the number of drawings of
a permutation, where the numbers *1-n* are listed on the top and bottom of
a rectangle, and a line joins *j* with its image *pi(j)*. This is a
special case of our problem.

This problem arose while examining the number of nonisomorphic drawings of
the complete graph. Heiko Harborth points out a similarity to *arrangements*
(sets of straight lines in the projective plane) and suggests that the problem
may be difficult. Valery Liskovets points out that the sequence
(1,1,2,8,62,...) appears in *The Encyclopedia of Integer Sequences* by
Sloane et al.(1995) #M1894. It was found by Knuth who was counting point
configurations. Valery also points out the related reference [B] which
describes the structure of intersection graphs and includes references to Gauss
codes.

**References:**

[B] A. Bouchet, Circle graph obstructions, *J. of Combin. Th. Ser B* **60**
(1994) 107-144.

[R] G. Ringel, Teilungen der Ebene durch Geraden oder topologische Geraden, *Mathematische
Zeitschrift* **64** (1955) 79-102.

Submitted by: Dan Archdeacon, Department of Math. and Stat., University of Vermont, Burlington, VT, USA 05405

Send comments to *dan.archdeacon@uvm.edu
*

August, 1995. Modified November 1998