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.
[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 firstname.lastname@example.org
August, 1995. Modified November 1998