Zeichnen von Graphen der begrenzten Kreuzungsnummer

Fárys Theorem besagt, dass ein einfacher planarer Graph ohne Kreuzungen gezeichnet werden kann, so dass jede Kante ein gerades Liniensegment ist.

Meine Frage ist, ob es einen analogen Satz für Graphen mit begrenzter Kreuzungszahl gibt . Können wir insbesondere sagen, dass ein einfacher Graph mit der Kreuzungszahl k so gezeichnet werden kann, dass die Zeichnung k Kreuzungen enthält und dass jede Kante für eine Funktion f höchstens eine Gradkurve f (k) ist?

EDIT: Wie David Eppstein bemerkt, ist leicht zu erkennen, dass Fárys Theorem eine Zeichnung eines Graphen mit der Kreuzungszahl k impliziert, so dass jede Kante eine polygonale Kette mit höchstens k Biegungen ist. Ich bin aber immer noch gespannt, ob jede Kante mit begrenzten Gradkurven gezeichnet werden kann. Hsien-Chih Chang weist darauf hin, dass f (k) = 1 ist, wenn k 0, 1, 2, 3 und ansonsten f (k)> 1 ist.

Wenn ein Graph eine begrenzte Kreuzungszahl hat, kann er mit dieser Anzahl von Kreuzungen im Polylinienmodell (dh jede Kante ist eine polygonale Kette, die in der Literatur zum Zeichnen von Graphen viel häufiger vorkommt als algebraische Kurven mit begrenztem Grad) mit einer begrenzten Anzahl von Biegungen gezeichnet werden pro Kante. Es gilt auch allgemeiner, wenn es eine begrenzte Anzahl von Kreuzungen pro Kante gibt. Um dies zu sehen, planarisieren Sie einfach das Diagramm (ersetzen Sie jede Kreuzung durch einen Scheitelpunkt) und wenden Sie dann Fáry an.

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

In der Arbeit Grenzen für geradlinige Kreuzungszahlen haben Bienstock und Dean dies bewiesen

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