<p>Let $cr(G)$ be the crossing number of a graph $G$, i.e. the minimum possible number of edge crossings over all valid drawings of $G$ in the plane.  In general the edges of $G$ may be represented as arcs rather than straight line segments; let $\overline{cr}(G)$ be the crossing number of $G$ when edges must be drawn as straight line segments.  Fáry's Theorem says that
$$cr(G) = 0 \iff \overline{cr}(G) = 0,$$
 but it is known that equality doesn't hold in general.  So, my question is whether there are any weaker constraints on the drawing where equality <em>does</em> hold in general:</p>

<blockquote>
  <p>What restrictions can we place on the edge arcs of graph drawings without affecting the crossing number?</p>
</blockquote>

<p>For example, can we always achieve minimum crossing number while drawing each edge curving monotonically in some direction?  What about drawing each edge as an algebraic curve?  I'd be interested in any results along these lines.</p>

CC BY-SA 4.0
2018-08-21T12:26:07.123Z
This does not answer your example questions, but this paper of Bienstock investigates the $t$-polygonal crossing number $\bar{cr}_t(G)$, where edges are allowed to bend $t$ times: https://link.springer.com/article/10.1007/BF02574701 He shows that for $t=\Theta(\sqrt{cr(G)}$, $\bar{cr}_t(G)=cr(G)$ and that the square root dependency is tight.
Arnaud
CC BY-SA 4.0
2018-08-21T20:25:13.223Z
That’s exactly the sort of thing I’m looking for. Thanks!
GMB
<planar-graphs><graph-drawing>
Fáry-Like Theorems for nonplanar graphs
GMB
# Fáry-Like Theorems for nonplanar graphs

(Asked by: username_0 on 2018-08-20)

Let $cr(G)$ be the crossing number of a graph $G$, i.e. the minimum possible number of edge crossings over all valid drawings of $G$ in the plane. In general the edges of $G$ may be represented as arcs rather than straight line segments; let $\overline{cr}(G)$ be the crossing number of $G$ when edges must be drawn as straight line segments. Fáry's Theorem says that
$$cr(G) = 0 \iff \overline{cr}(G) = 0,$$
but it is known that equality doesn't hold in general. So, my question is whether there are any weaker constraints on the drawing where equality *does* hold in general:

> What restrictions can we place on the edge arcs of graph drawings without affecting the crossing number?

For example, can we always achieve minimum crossing number while drawing each edge curving monotonically in some direction? What about drawing each edge as an algebraic curve? I'd be interested in any results along these lines.

**Tags:** planar-graphs, graph-drawing

> **Comments:**
> **username_1**: This does not answer your example questions, but this paper of Bienstock investigates the $t$-polygonal crossing number $\bar{cr}_t(G)$, where edges are allowed to bend $t$ times: https://link.springer.com/article/10.1007/BF02574701 He shows that for $t=\Theta(\sqrt{cr(G)}$, $\bar{cr}_t(G)=cr(G)$ and that the square root dependency is tight.  
> **username_0**: That’s exactly the sort of thing I’m looking for. Thanks!  

---

## 0 answers

