The Crossing Number of Single-Pair-Seq-Shellable Drawings of Complete Graphs
share
The Harary-Hill Conjecture states that for n≥ 3 every drawing of K_n has at least H(n) := 1/4n/2n-1/2n-2/2n-3/2 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 single-pair-seq-shellable drawings. We prove the Harary-Hill Conjecture for this new class using novel results on triple cumulated k-edges. So far, all approaches for proving the Harary-Hill Conjecture for specific classes rely on a globally 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 a fixed reference face.
READ FULL TEXT