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:

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.

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.

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. 

Submitted by: Dan Archdeacon, Department of Math. and

Stat., University of Vermont, Burlington, VT, USA 05405