9
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Thanks. Is there an example which shows that one cannot, in general, draw with minimum number of crossings using straight line segment edges? $\endgroup$ – arnab Feb 21 '11 at 9:08
  • $\begingroup$ @arnab: see Hsien-Chih's answer. $\endgroup$ – David Eppstein Feb 21 '11 at 16:27
12
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks! This then answers the question in my comment to David's answer. I'm still interested in knowing if my original question has been studied. $\endgroup$ – arnab Feb 21 '11 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.