The Crossing Number of Seq-Shellable Drawings of Complete Graphs
share
The Harary-Hill conjecture states that for every n>0 the complete graph on n vertices K_n, the minimum number of crossings over all its possible drawings equals H(n) := 1/4n/2n-1/2n-2/2n-3/2. So far, the lower bound of the conjecture could only be verified for arbitrary drawings of K_n with n≤ 12. In recent years, progress has been made in verifying the conjecture for certain classes of drawings, for example 2-page-book, x-monotone, x-bounded, shellable and bishellable drawings. Up to now, the class of bishellable drawings was the broadest class for which the Harary-Hill conjecture has been verified, as it contains all beforehand mentioned classes. In this work, we introduce the class of seq-shellable drawings and verify the Harary-Hill conjecture for this new class. We show that bishellability implies seq-shellability and exhibit a non-bishellable but seq-shellable drawing of K_11, therefore the class of seq-shellable drawings strictly contains the class of bishellable drawings.
READ FULL TEXT