Pair crossing number, cutwidth, and good drawings on arbitrary point sets

Determining whether there exists a graph such that its crossing number and pair crossing number are distinct is an important open problem in geometric graph theory. We show that $\mathit{\text{cr}}(G)=O((G{)}^{3\mathrm{/}2})$ for every graph $G$, this improves the previous best bound by a logarithmic factor. Answering a question of Pach and Tóth, we prove that the bisection width (and, in fact, the cutwidth as well) of a graph $G$ with degree sequence $d_1,d_2,\dots ,d_n$ satisfies $(G)=O\left(\sqrt{(G)+{\sum }_{k=1}^n{d}_k^2}\right)$. Then we show that there is a constant $C\ge 1$ such that the following holds: For any graph $G$ of order $n$ and any set $S$ of at least $n^C$ points in general position on the plane, $G$ admits a straight-line drawing which maps the vertices to points of $S$ and has no more than $O(\log n\cdot ((G)+{\sum }_{k=1}^n{d}_k^2))$ crossings. Our proofs rely on a modified version of a separator theorem for string graphs by Lee, which might be of independent interest.