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.

  • 1
    $\begingroup$ 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: 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. $\endgroup$ – Arnaud Aug 21 '18 at 12:26
  • $\begingroup$ That’s exactly the sort of thing I’m looking for. Thanks! $\endgroup$ – GMB Aug 21 '18 at 20:25

Your Answer

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

Browse other questions tagged or ask your own question.