Non-Shellable Drawings of Kn with Few Crossings
Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández‐Merchant, Pedro A. Ramos, Birgit Vogtenhuber · 2014
In the early 60s, Harary and Hill conjectured H(n):= 1 4bn2 cbn12 cbn22 cbn32 c to be the minimum number of crossings among all drawings of the complete graph Kn. It has recently been shown that this conjecture holds for so-called shellable drawings of Kn. For n 11 odd, we construct a non-shellable family of drawings of Kn with exactly H(n) crossings. In par-ticular, every edge in our drawings is intersected by at least one other edge. So far only two other families were known to achieve the conjectured minimum of crossings, both of them being shellable. 1