Connect the dots

It turns out this is a well-studied and notoriously difficult problem in combinatorial geometry. While it is tempting to ask the same question for 8, 9, or even $n$ points, we’ll see that the problem gets very difficult very quickly, and the answer for general $n$ is not actually known!

First, we’ll get some terminology out of the way:

• A complete graph is a graph with every possible edge drawn in. The complete graph with $n$ nodes is denoted $K_n$.
• A Hamiltonian cycle is a path through the graph that finishes where it started and visits every node exactly once. For the graph $K_n$, there are $\frac{1}{2}(n-1)!$ possible Hamiltonian cycles since we can fix the starting node and then there are $n-1$ nodes left to order. We divide by two because each cycle is counted twice (can be traversed forwards or backwards).
• A realization of a graph is a particular way of arranging the nodes. Realizations are important because we care about whether edges cross or not; sometimes two different arrangements of the same graph will have different numbers of edge crossings.
• The rectilinear crossings of a graph realization $G$ is the number of times edges cross when we connect the nodes with straight lines. We’ll denote this number $\mathrm{rcr}(G)$.
• The crossing-free Hamiltonian cycles of a graph realization $G$ is the number of different Hamiltonian cycles of $G$ that do not contain any edges that cross each other. We’ll denote this number $\mathrm{cfhc}(G)$. These are also called “spanning cycles” or “simple polygonalizations” depending on who you ask.

For a simple example, let’s start with $K_4$, the complete graph on 4 nodes. Although there are infinitely many ways to realize this graph (since we can arrange the 4 points in infinitely many ways), rearrangements of the points that preserve how the edges intersect one another are all equivalent for our purpose (this is an example of an equivalence class). So we only need to consider one representative from each class. These representative realizations are called order types. It turns out $K_4$ has two order types:

The first order type has no crossings ($\mathrm{rcr}(G)=0$) and three possible crossing-free Hamiltonian cycles. Here are the cycles:

The second order type has one crossing ($\mathrm{rcr}(G)=1$) and only one possible crossing-free Hamiltonian cycle:

The bad news…

Unfortunately, things get difficult from this point on as we add more nodes:

• The number of order types for $K_n$ grows rapidly with $n$. For $n\ge 3$, they are: $\{1, 2, 3, 16, 135, 3315, 158817, 14309547, 2334512907,\dots\}$. This sequence is in OEIS. There is no known general formula.
• The minimal rectilinear crossing number for $K_n$ over all possible realizations for $n\ge 3$ is: $\{0, 0, 1, 3, 9, 19, 36, 62, 102, 153,\dots\}$. This sequence is also in OEIS. No known formula known for this one either.
• Finally, the minimal number of crossing-free Hamiltonian cycles for $K_n$ for $n \ge 3$ is: $\{1, 3, 8, 29, 92, 339, 1282, 4994,\dots\}$. And this is also in OEIS. You guessed it; no known formula.

These problems are related but different. For example, we might expect realizations with smaller crossing numbers to contain more crossing-free Hamiltonian cycles, since it is easier to avoid intersections when there are fewer of them. But this is not always the case. We might also expect realizations with more symmetry to contain more cycles; also not true in general. What I’m trying to get at is that there are no (known) tricks we can use to reduce this problem to a simpler one. Unfortunately, it appears the only way to solve such problems is to enumerate all order types (even this is difficult!), then enumerate all possible cycles, keeping only the ones that are crossing-free.

Many other variants are just as difficult: computing the crossing number (with curved edges allowed), the number of triangulations, the minimum number of convex polygons needed for a decomposition of the convex hull, and more. These sorts of problems belong to a branch of mathematics called combinatorial geometry. A great deal of research on the topic of order types, crossing numbers, and more, has been conducted by Prof. Oswin Aichholzer and colleagues. If you’re interested in learning more, I recommend checking out his webpage here, which contains an up-to-date database of solutions to many of these and related problems for small-ish $n$.

Visualizing the solutions

I used the point layouts provided on Prof. Aichholzer’s website and wrote some Python code to visualize the results. As a warm-up, I started with the case $K_5$.

The order types are sorted by their rectilinear crossing number. The one with the most crossing-free Hamiltonian cycles is the first one. Here they are:

Six nodes

Here are the 16 order types for $K_6$:

Here are the 29 crossing-free Hamiltonian cycles for the maximal configuration:

Seven nodes

Here are the 135 order types for $K_7$. Interestingly, there are three different realizations for the minimal rectilinear crossing number of $9$, and the most symmetric one (the first one) is not the one with the most crossing-free Hamiltonian cycles!

And here are the 92 crossing-free Hamiltonian cycles for the maximal configuration:

More nodes

The solutions get too large to visualize beyond 7 nodes, but here are the results for $n \leq 10$, courtesy once again of Prof. Aichholzer’s webpage. “CFHC” stands for “crossing-free Hamiltonian cycles”.

Number of nodes	Order types	Max CFHC
3	1	1
4	2	3
5	3	8
6	16	29
7	135	92
8	3,315	339
9	158,817	1,282
10	14,309,547	4,994

The Python code I wrote to produce all the figures is available here.