No label defined (Q4812913)

A drawing of a graph is outerplanar, if the vertices of the graph are placed on a circle and edges are drawn in straight line segments. The outerplanar crossing number of a graph is the minimum number of crossing edge pairs over all outerplanar drawings of the graph. (The outerplanar crossing number has also been called convex crossing number, and it is equal to the 1-page crossing number.) The paper sets a lower bound \(n(m-1)(2mn-3m-n)/12\) for the outerplanar crossing number of the complete bipartite graph \(K_{n,m}\) (\(m\leq n\)), and shows that this bound is exact if \(m\) divides \(n\). This significantly improves on an earlier lower bound \({m^3n^3\over 37(m+n)^2}\) (note that the exponent in the denominator is 2, not 3).