Tracer des graphiques du numéro de passage limité

Le théorème de Fáry dit qu'un simple graphique planaire peut être tracé sans croisements de sorte que chaque arête est un segment de ligne droite.

Ma question est de savoir s'il existe un théorème analogue pour les graphiques de nombre de croisements bornés . Plus précisément, pouvons-nous dire qu'un simple graphique avec le nombre de croisements k peut être tracé de sorte qu'il y ait k croisements dans le dessin et que chaque arête soit une courbe de degré au plus f (k) pour une fonction f?

EDIT: Comme le remarque David Eppstein, on voit facilement que le théorème de Fáry implique un dessin d'un graphique avec le nombre de croisement k de sorte que chaque arête est une chaîne polygonale avec au plus k courbures. Je suis toujours curieux de savoir si chaque arête peut être dessinée avec des courbes de degré bornées. Hsien-Chih Chang souligne que f (k) = 1 si k est 0, 1, 2, 3 et f (k)> 1 sinon.

Si un graphique a un nombre de croisements borné, il peut être dessiné avec ce nombre de croisements dans le modèle de polyligne (c'est-à-dire que chaque arête est une chaîne polygonale, beaucoup plus courante dans la littérature de dessin de graphes que les courbes algébriques à degrés bornés) avec un nombre borné de courbes par bord. C'est également vrai plus généralement s'il y a un nombre limité de croisements par bord. Pour le voir, il suffit de planariser le graphique (remplacer chaque croisement par un sommet) puis d'appliquer Fáry.

$s_i$$e_i$$s_i$$p_i$$e_i$$e_i$$p=\epsilon-\prod_i p_i$$\epsilon$$p=0$

$\overline{\mathsf{cr}}(G)$$G$$\mathsf{cr}(G)$$\overline{\mathsf{cr}}(G) \geq \mathsf{cr}(G)$$\overline{\mathsf{cr}}(G) = \mathsf{cr}(G)$$\mathsf{cr}(G) \leq k$$k$

Dans l'étude Limites des nombres de croisements rectilignes , Bienstock et Dean ont prouvé que

$k \leq 3$$\overline{\mathsf{cr}}(G) = \mathsf{cr}(G)$$k \geq 4$$G_n$$\mathsf{cr}(G) = 4$$\overline{\mathsf{cr}}(G) \geq n$

$\mathsf{cr}(G) \leq 3$

$\overline{\mathsf{cr}}(G) \neq \mathsf{cr}(G)$$\mathsf{cr}(K_8) = 18$$\overline{\mathsf{cr}}(K_8) = 19$