<p>This is known as the <em>rectilinear crossing number</em> $\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$.</p>

<p>In the paper <a href="http://portal.acm.org/citation.cfm?id=175284.175304" rel="nofollow noreferrer">Bounds for rectilinear crossing numbers</a>, Bienstock and Dean proved that </p>

<blockquote>
  <p><strong>Theorem.</strong> 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$.</p>
</blockquote>

<p>See <a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3EAAB205E7D88A18E7B6DE8AD0AFB58A?doi=10.1.1.155.5058&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">A survey on crossing numbers</a> 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$.</p>

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

<p><img src="https://i.sstatic.net/j8qxq.jpg" width="170">
<img src="https://i.sstatic.net/6Y6Fm.jpg" width="165"></p>

CC BY-SA 2.5
2011-02-21T14:56:16.010Z
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.
arnab
CC BY-SA 2.5
2011-02-21T14:43:49.413Z
2011-02-21T15:08:15.510Z
2011-02-21T15:08:15.510Z
Hsien-Chih Chang 張顯之
<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-02-21T09:08:07.113Z
Thanks.  Is there an example which shows that one cannot, in general, draw with minimum number of crossings using straight line segment edges?
arnab
CC BY-SA 2.5
2011-02-21T16:27:45.800Z
@arnab: see Hsien-Chih's answer.
David Eppstein
CC BY-SA 2.5
2011-02-21T06:56:33.573Z
2011-03-02T20:31:08.923Z
2011-03-02T20:31:08.923Z
David Eppstein
<p><a href="http://en.wikipedia.org/wiki/F%C3%A1ry%27s_theorem" rel="nofollow">Fáry's theorem</a> says that a simple planar graph can be drawn without crossings so that each edge is a straight line segment. </p>

<p>My question is whether there is an analogous theorem for graphs of bounded <a href="http://en.wikipedia.org/wiki/Crossing_number_(graph_theory)" rel="nofollow">crossing number</a>.  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?</p>

<p>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.</p>

<graph-theory><co.combinatorics><planar-graphs>
Drawing graphs of bounded crossing number
arnab
# Drawing graphs of bounded crossing number

(Asked by: username_0 on 2011-02-21)

[Fáry's theorem](http://en.wikipedia.org/wiki/F%C3%A1ry%27s_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](http://en.wikipedia.org/wiki/Crossing_number_(graph_theory)). 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.

**Tags:** graph-theory, co.combinatorics, planar-graphs

---

## 2 answers

### Answer by username_2 on 2011-02-21. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks.  Is there an example which shows that one cannot, in general, draw with minimum number of crossings using straight line segment edges?  
> **username_2**: @arnab: see Hsien-Chih's answer.  

---

### Answer by username_1 on 2011-02-21. Score: 12

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](http://portal.acm.org/citation.cfm?id=175284.175304), 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](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3EAAB205E7D88A18E7B6DE8AD0AFB58A?doi=10.1.1.155.5058&rep=rep1&type=pdf) 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$.

![](https://i.sstatic.net/j8qxq.jpg)
![](https://i.sstatic.net/6Y6Fm.jpg)

> **Comments:**
> **username_0**: 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.  

---

