The rectilinear crossing number vs crossing number

Question

The rectilinear crossing number of a graph $G$ denoted by $\overline{cr}(G)$ on $n$ vertices is the minimum number of crossings between edges of $G$ among all possible drawing of $G$ such that all its edges are straight. As opposed to the crossing number $cr(G)$, which is the minimal number of crossings of edges of $G$ in all possible drawing of $G$.

For a planar graphs $G$, $cr(G)=\overline{cr}(G)$. Is there an example in which the two are not the same? Is there an example in which $\overline{cr}(G)>> cr(G)$?

Answer 1

Yes, and yes.

The paper Bounds for Rectilinear Crossing Number by Bienstock and Dean gives the following construction for a graph with crossing number $4$ but arbitrarily large rectilinear crossing number.

Start with the following graph:

It has blue edges and red edges. In the rectilinear picture drawn, some red edges and blue edges intersect. It's possible to draw some of the red edges as arcs to get a different picture, in which the red edges avoid crossing any blue edges, and have only 4 crossings. But it's not possible to avoid all red-blue crossings with straight edges.

Now extend this graph by replacing every blue edge $xy$ with $m$ edge-disjoint paths of length $2$ starting at $x$ and ending at $y$. This has the effect of making blue edges count $m$ times as much. So:

• the picture with $4$ red crossings (which cannot be realized with straight edges) still has crossing number $4$,
• but the straight-line drawing above no longer has crossing number $12$ but $4m+8$,
• and in general, there is no straight-line drawing that gets the crossing number below $m$, because a blue edge has to cross a red edge.