I want to show that for any n and m, 5n $\leq$ m $\leq$ $\binom n2$, $\exists$ a graph with n vertices, m edges, and crossing number O($m^3$/$n^2$). I've been given the hint that I should try to sparsify the complete graph by only keeping edges that connect vertices which are at most a fixed distance in the cyclic order. However, I'm very confused as to where to start with this. Could someone please point me in the right direction?
Edit: A classmate has advised me to use m/n as the fixed distance mentioned above, but I still can't see where to go from there.
Taking the hint that you've been given, let's draw the graph below, with $n$ vertices and with edges connecting those vertices that are $k$ or fewer steps apart in the cyclic order (so that there are $m = kn$ edges total):
The picture above (for $n=16$ and $k = 5$) is the natural drawing of this graph to take, and it suffices to prove an $O(n^3/m^2)$ upper bound on its crossing number.
Since we're not looking for the best constant inside the $O(n^3/m^2)$, we can even be a bit sloppy about counting the crossings. Just put an upper bound on the number of crossings for one edge: $2k^2$ is easy to do, though I think something like $k^2$ is true if you're careful. (Consider how you'd bound the number of black edges that pass through the red edge in the diagram above.) Then multiply by the number of edges, and express the result in terms of $n$ and $m$.