2018/03/20 by Petra Mutzel, Lutz Oettershagen, Mutzel, Petra +1 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #cs.CG #math.CO
paper · pdf · doi:10.48550/arxiv.1803.07515
arxiv created 2018/03/20 · arxiv updated 2018/03/21
The Harary-Hill conjecture states that for every n>0 the complete graph on n vertices Kn, the minimum number of crossings over all its possible drawings equals H(n) := (1)/(4)\lfloor(n)/(2)\rfloor\lfloor(n-1)/(2)\rfloor\lfloor(n-2)/(2)\rfloor\lfloor(n-3)/(2)\rfloor. So far, the lower bound of the conjecture could only be verified for arbitrary drawings of Kn 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 K11, therefore the class of seq-shellable drawings strictly contains the class of bishellable drawings.