Drawing graphs of bounded crossing number

Question

Fáry's theorem says that a simple planar graph can be drawn without crossings so that each edge is a straight line segment.

My question is whether there is an analogous theorem for graphs of bounded crossing number. Specifically, can we say that a simple graph with crossing number k can be drawn so that there are k crossings in the drawing and so that each edge is a curve of degree at most f(k) for some function f?

EDIT: As David Eppstein remarks, it is readily seen that Fáry's theorem implies a drawing of a graph with crossing number k so that each edge is a polygonal chain with at most k bends. I'm still curious though whether each edge can be drawn with bounded degree curves. Hsien-Chih Chang points out that f(k) = 1 if k is 0, 1, 2, 3, and f(k) > 1 otherwise.

Answer 1

If a graph has bounded crossing number it can be drawn with that number of crossings in the polyline model (i.e. each edge is a polygonal chain, much more common in the graph drawing literature than bounded-degree algebraic curves) with a bounded number of bends per edge. It's also true more generally if there is a bounded number of crossings per edge. To see this, just planarize the graph (replace each crossing by a vertex) and then apply Fáry.

Now, to use this to answer your actual question, what you need to do is to find an algebraic curve that is arbitrarily close to a given polyline, with degree bounded by a function of the number of polyline bends. This can also be done, fairly easily. For instance: for each segment $s_i$ of the polyline, let $e_i$ be an ellipse with high eccentricity that is very close to $s_i$, and let $p_i$ be a quadratic polynomial that is positive outside $e_i$ and negative inside $e_i$. Let your overall polynomial take the form $p=\epsilon-\prod_i p_i$ where $\epsilon$ is a small positive real number. Then one component of the curve $p=0$ will lie a little outside the union of the ellipses and can be used to substitute for the polyline; its degree will be twice the number of ellipses, which is linear in the number of crossings per edge.

Answer 2

This is known as the rectilinear crossing number $\overline{\mathsf{cr}}(G)$, which is the minimum number of crossings among all possible straight-line drawings of the graph $G$. Compare to the normal crossing number $\mathsf{cr}(G)$, one can see that $\overline{\mathsf{cr}}(G) \geq \mathsf{cr}(G)$. And your question is essentially as the same as asking whether $\overline{\mathsf{cr}}(G) = \mathsf{cr}(G)$ if $\mathsf{cr}(G) \leq k$ for some constant $k$.

In the paper Bounds for rectilinear crossing numbers, Bienstock and Dean proved that

Theorem. If $k \leq 3$, we have $\overline{\mathsf{cr}}(G) = \mathsf{cr}(G)$. And for $k \geq 4$, there are graphs $G_n$ with $\mathsf{cr}(G) = 4$ and $\overline{\mathsf{cr}}(G) \geq n$.

See A survey on crossing numbers by Richter and Salazar for reference. So if there is a variant of the Fáry theorem on graphs with bounded crossing numbers, it should be constrained with $\mathsf{cr}(G) \leq 3$.

For a small example with $\overline{\mathsf{cr}}(G) \neq \mathsf{cr}(G)$, consider complete graph on 8 vertices. It has $\mathsf{cr}(K_8) = 18$ and $\overline{\mathsf{cr}}(K_8) = 19$.