The Crossing Number of Seq-Shellable Drawings of Complete Graphs

摘要

The Harary-Hill conjecture states that for every n > 3 the number of crossings of a drawing of the complete graph K_n is at least H(n):=1/4「n/2」「(n-1)/2」「(n-2)/2」「(n-3)/2」 So far, 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.