Counting crossings of a particular complete bipartite graph

Question

This type of complete bipartite graph has two vertex sets $(V,U)$ where $V$ has points $v_n$ along a straight line parallel to the set of points $u_m$. How should I go about finding a general formula to count the amount of crossing in this particular type of graph? There are 18 crossings, not including crossings that occur at the sets of vertices on the top and bottom lines themselves, for $K_{4,3}$.

$K_{4,3}$" />

Answer 1

Let the graph be $K_{n,m}$. If you fix the $i$-th vertex on the upper line and the $j$-th on the lower line, then all lines formed with vertices to the left of $i$ and the right of $j$ will touch this line and also all the lines formed to the right of $i$ and the left of $j$ will touch this line, and so the total crossing will be

$$\frac{1}{2}\sum _{\substack{1\leq i\leq n\\1\leq j\leq m}}(i-1)(m-j)+(n-i)(j-1)$$

It is half because you are actually counting each crossing twice.

This is equivalent to choose two points on the upper line and two points on the lower line (join them in a cross) so it will be $$\binom{n}{2}\binom{m}{2}.$$