Motivated by the successful application of geometry to proving the Harary--Hill conjecture for “pseudolinear” drawings of $K_n$, we introduce “pseudospherical” drawings of graphs. A spherical drawing of a graph $G$ is a drawing in the unit sphere $\mathbb{S}^2$ in which the vertices of $G$ are represented as points---no three on a great circle---and the edges of $G$ are shortest-arcs in $\mathbb{S}^2$ connecting pairs of vertices. Such a drawing has three properties: (1) every edge $e$ is contained in a simple closed curve $\gamma_e$ such that the only vertices in $\gamma_e$ are the ends of $e$; (2) if $e\ne f$, then $\gamma_e\cap\gamma_f$ has precisely two crossings; and (3) if $e\ne f$, then $e$ intersects $\gamma_f$ at most once, in either a crossing or an end of $e$. We use properties (1)--(3) to define a pseudospherical drawing of $G$. Our main result is that for the complete graph, properties (1)--(3) are equivalent to the same three properties but with “precisely two crossings” in (2) replaced by “at most two crossings.” The proof requires a result in the geometric transversal theory of arrangements of pseudocircles. This is proved using the surprising result that the absence of special arcs (coherent spirals) in an arrangement of simple closed curves characterizes the fact that any two curves in the arrangement have at most two crossings. Our studies provide the necessary ideas for exhibiting a drawing of $K_{10}$ that has no extension to an arrangement of pseudocircles and a drawing of $K_9$ that does extend to an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles crossing twice.

The Harary--Hill conjecture, still open after more than 50 years, asserts that the crossing number of the complete graph $K_n$ is \(H(n) := \frac 1 4 łfloor\fracn2\rfloor łfloor\fracn-12\rfloor łfloor\fracn-22\rfloor łfloor\fracn-32\rfloor.\) Ábrego et al. [ Discrete Comput. Geom., 52 (2014), pp. 743--753] introduced the notion of shellability of a drawing $D$ of $K_n$. They proved that if $D$ is $s$-shellable for some $s\geq\lfloor\frac{n}{2}\rfloor$, then $D$ has at least $H(n)$ crossings. This is the first combinatorial condition on a drawing that guarantees at least $H(n)$ crossings. In this work, we generalize the concept of $s$-shellability to bishellability, where the former implies the latter in the sense that every $s$-shellable drawing is, for any $b \leq s-2$, also $b$-bishellable. Our main result is that $(\lfloor \frac{n}{2} \rfloor-2)$-bishellability of a drawing $D$ of $K_n$ also guarantees, with a simpler proof than for $s$-shellability, that $D$ has at least $H(n)$ crossings. We exhibit a drawing of $K_{11}$ that has $H(11)$ crossings, is 3-bishellable, and is not $s$-shellable for any $s\geq5$. This shows that we have properly extended the class of drawings for which the Harary--Hill conjecture is proved. Moreover, we provide an infinite family of drawings of $K_n$ that are $(\lfloor \frac{n}{2} \rfloor-2)$-bishellable, but not $s$-shellable for any $s\geq\lfloor\frac{n}{2}\rfloor$.

It has been long conjectured that the crossing number $\Cr(K_{m,n})$ of the complete bipartite graph $K_{m,n}$ equals the Zarankiewicz number $Z(m,n):= \floor{\frac{m-1}{2}} \floor{\frac{m}{2}} \floor{\frac{n-1}{2}} \floor{\frac{n}{2}}$. Another longstanding conjecture states that the crossing number $\Cr(K_n)$ of the complete graph $K_n$ equals $Z(n):=\frac{1}{4}\smallfloor{\frac{n}{2}} \smallfloor{\frac{n-1}{2}} \smallfloor{\frac{n-2}{2}}\smallfloor{\frac{n-3}{2}}$. In this paper we show the following improved bounds on the asymptotic ratios of these crossing numbers and their conjectured values: \begin{itemize} \item[(i)] for each fixed $m\ge 9$, $\lim_{n\to\infty} \Cr(K_{m,n})/Z(m,n) \ge 0.83m/(m-1)$; \item[(ii)] $\lim_{n\to\infty} \Cr(K_{n,n})/Z(n,n) \ge 0.83$; and \item[(iii)] $\lim_{n\to\infty} \Cr(K_{n})/Z(n) \ge 0.83$. \end{itemize} The previous best known lower bounds were $0.8m/(m-1), 0.8$, and $0.8$, respectively. These improved bounds are obtained as a consequence of the new bound $\Cr(\ksn) \ge 2.1796n^2 - 4.5n$. To obtain this improved lower bound for $\Cr(\ksn)$, we use some elementary topological facts on drawings of $K_{2,7}$ to set up a quadratic program on $6!$ variables whose minimum p satisfies $\Cr(\ksn) \ge (p/2)n^2 - 4.5n$, and then use state-of-the-art quadratic optimization techniques combined with a bit of invariant theory of permutation groups to show that $p \ge 4.3593$.