This paper, recently published by Petra Mutzel and Lutz Oettershagen, makes a significant dent in one of the most stubborn problems in topological graph theory: the Harary-Hill Conjecture. By introducing a new class of graph drawings and developing more flexible counting techniques, the authors have expanded the set of conditions under which we can prove a drawing is "crossing-optimal."
TL;DR
The authors prove the Harary-Hill Conjecture for a new, broader class of graph drawings called semi-pair-shellable drawings. They achieve this by moving beyond the rigid requirement of a "globally fixed reference face" and utilizing a novel mathematical framework involving triple-cumulated $k$-edges and $k$-deviations.
What Problem Does This Paper Address?
The crossing number of a graph, $cr(G)$, is the minimum number of edge crossings possible in any drawing of that graph in the plane. For the complete graph $K_n$ (where every vertex is connected to every other vertex), the Harary-Hill Conjecture (1963) provides a specific formula, $H(n)$, for this minimum value.
While $H(n)$ has been verified for small graphs ($n \le 12$), a general proof remains elusive. The standard strategy is to prove the conjecture for specific classes of drawings. The most general class previously known was "seq-shellable" drawings. However, proofs for these classes were hampered by a major technical limitation: they required a single "reference face" to remain fixed throughout the entire proof, even as vertices were removed to analyze subdrawings. This paper aims to break that "fixed face" bottleneck.
Methods
The authors employ several sophisticated combinatorial tools:
- Triple Cumulated $k$-edges: A $k$-edge is an edge that divides the remaining vertices into two sets, one of size $k$. By "cumulating" these counts three times (summing the sums of the sums), the authors create a powerful metric that directly relates to the total crossing number.
- Semi-Pair-Shellability: They define a new class of drawings. Unlike standard shellability, which requires removing vertices one by one in a specific order, semi-pair-shellability allows for "pair-sequences." This provides more flexibility in how a drawing can be decomposed and analyzed.
- Local Reference Face Changes: This is the paper's most significant technical leap. The authors prove that for graphs with an odd number of vertices, certain cumulated $k$-edge values are invariant regardless of which face incident to a vertex is chosen as the reference. This allows them to "hop" between different reference faces as they move through the graph's structure.
- $k$-Deviations: They introduce $\Delta_k(D)$, a measure of the difference between a drawing's actual $k$-edge count and the "ideal" count of a crossing-minimal drawing.
Key Insights and Ideas
- Breaking the Global Constraint: The realization that the reference face doesn't have to be globally fixed is a game-changer. It allows researchers to select the most advantageous face locally for each subdrawing, as illustrated in the transition between Figure 2 and Figure 3.

- The Power of Triples: Moving from double to triple cumulated $k$-edges provides a more stable recursive structure for induction proofs.
- A New Class Hierarchy: The authors demonstrate that semi-pair-shellable drawings are a distinct class. While they intersect with seq-shellable drawings, they are not a subset, meaning this proof covers drawings that were previously unproven.
Key Results
- Theorem 17: The authors formally prove that for any semi-pair-shellable drawing $D$ of $K_n$, the crossing number $cr(D)$ is at least $H(n)$, confirming the Harary-Hill Conjecture for this class.
- Conjecture 2: They propose a new conjecture regarding $k$-deviations: $\hat{\Delta}_{k}(D) \ge \bar{\Delta}_{k}(D)$. They show that if this relatively simple inequality holds for all good drawings, the Harary-Hill Conjecture would be proven for a massive, nearly universal class of drawings.
- Verification of Invariance: They provide a rigorous proof (Lemma 12) that for odd $n$, the double cumulated invariant $k$-edge value is independent of the choice of reference face incident to a vertex.
Limitations and Future Work
The primary limitation is that semi-pair-shellability is currently only defined for graphs with an odd number of vertices. Extending these definitions and the invariance proofs to even $n$ is a clear next step.
Furthermore, the authors acknowledge that even this new class doesn't cover all possible optimal drawings. Some optimal drawings have faces that only touch a single vertex, making them resistant to current shellability-based techniques. The ultimate "holy grail" remains proving the authors' own Conjecture 2, which would likely provide the final bridge to a general proof of the Harary-Hill Conjecture.
Summary updated