The Crossing Number of Semi-Pair-Shellable Drawings of Complete Graphs

Petra Mutzel, Lutz Oettershagen

Introduction

The crossing number of a graph, denoted $cr(G)$, is the minimum number of edge crossings in any drawing of $G$ in the plane. For complete graphs $K_n$, the Harary-Hill Conjecture posits that the minimum crossing number is given by the formula:

$$H(n) = \frac{1}{4} \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor \lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor$$

While this conjecture has stood since the 1960s, proving it for all possible drawings remains an open challenge. Recent progress has focused on specific classes of drawings, such as shellable or monotone drawings. This paper, presented at the 30th Canadian Conference on Computational Geometry (CCCG 2018), introduces a new, broader class called semi-pair-shellable drawings.

Breaking Global Constraints

A significant hurdle in previous proofs was the reliance on a "globally fixed reference face." In these frameworks, the entire drawing must maintain a specific structural relationship with a single outer boundary. The authors break this limitation by allowing for "local" changes to the reference face during the proof process.

Figure 2: Illustrating k-edges and vertex removal relative to a reference face F.

Methodology and Key Innovations

The authors utilize the theory of $k$-edges. An edge is defined as a $k$-edge if it partitions the remaining vertices into sets of size $k$ and $n-k-2$ relative to a specific reference face. To achieve their results, they introduced several novel mathematical tools:

  • Triple Cumulated $k$-edges: A refined summation technique for tighter lower bounds on crossings.
  • Semi-Pair-Shellability: A property where vertices are removed in pairs (a "pair-sequence"), allowing the reference face to shift dynamically rather than staying fixed.
  • $k$-deviations: A metric quantifying the gap between a drawing's actual $k$-edge count and the theoretical optimum predicted by Harary-Hill.

The core innovation lies in the ability to "hop" between reference faces. As shown in Figure 4, the analysis can transition from one face $F$ to an adjacent face $F'$, relaxing the rigid constraints of earlier methods.

Figure 4: The transition between reference faces F and F' in a complex drawing.

Results and Implications

The primary result, Theorem 15, states that any semi-pair-shellable drawing of $K_n$ satisfies the Harary-Hill Conjecture: $cr(D) \geq H(n)$. This significantly expands the set of drawings for which the conjecture is known to hold. Notably, the authors demonstrate that semi-pair-shellable drawings are a strictly larger class than previously studied "seq-shellable" drawings, providing a specific example of a $K_{11}$ drawing that is semi-pair-shellable but not seq-shellable.

Conclusion and Future Directions

While this work represents a major step forward, the Harary-Hill Conjecture is not yet fully resolved. The current definition of semi-pair-shellability is primarily optimized for graphs with an odd number of vertices; extending these results to even $n$ remains an open challenge. Additionally, the authors propose a new "Deviation Conjecture" regarding the behavior of $k$-deviations, which could further generalize the classes of drawings that meet the $H(n)$ bound.

Summary updated

Abstract

The Harary-Hill Conjecture states that for $n\geq 3$ every drawing of $K_n$ has at least \begin{align*} H(n) := \frac{1}{4}\Big\lfloor\frac{n}{2}\Big\rfloor\Big\lfloor\frac{n-1}{2}\Big\rfloor\Big\lfloor\frac{n-2}{2}\Big\rfloor\Big\lfloor\frac{n-3}{2}\Big\rfloor \end{align*} crossings. In general the problem remains unsolved, however there has been some success in proving the conjecture for restricted classes of drawings. The most recent and most general of these classes is seq-shellability. In this work, we improve these results and introduce the new class of semi-pair-shellable drawings. We prove the Harary-Hill Conjecture for this new class using novel results on $k$-edges. So far, approaches for proving the Harary-Hill Conjecture for specific classes rely on a fixed reference face. We successfully apply new techniques in order to loosen this restriction, which enables us to select different reference faces when considering subdrawings. Furthermore, we introduce the notion of $k$-deviations as the difference between an optimal and the actual number of $k$-edges. Using $k$-deviations, we gain interesting insights into the essence of $k$-edges, and we further relax the necessity of fixed reference faces.
BibTeX
@inproceedings{mutzel2018crossing,
  author = {Petra Mutzel and Lutz Oettershagen},
  title = {{The Crossing Number of Semi-Pair-Shellable Drawings of Complete Graphs}},
  booktitle = {CCCG},
  year = {2018},
}
Figure