Rysowanie wykresów ograniczonej liczby skrzyżowań

Twierdzenie Fáry'ego mówi, że prosty wykres płaski można narysować bez przecięć, tak że każda krawędź jest odcinkiem linii prostej.

Moje pytanie brzmi, czy istnieje analogiczne twierdzenie dla grafów ograniczonej liczby skrzyżowań . W szczególności, czy możemy powiedzieć, że można narysować prosty wykres z liczbą przecięcia k, aby na rysunku było k skrzyżowań, a każda krawędź była krzywą stopnia co najwyżej f (k) dla niektórych funkcji f?

EDYCJA: Jak zauważa David Eppstein, łatwo zauważyć, że twierdzenie Fáryego oznacza rysunek wykresu z przecinającą się liczbą k, tak że każda krawędź jest łańcuchem wielokątnym o co najwyżej k zagięciach. Nadal jestem ciekawy, czy każdą krawędź można narysować za pomocą krzywych stopni ograniczonych. Hsien-Chih Chang wskazuje, że f (k) = 1, jeśli k wynosi 0, 1, 2, 3, a f (k)> 1 w przeciwnym razie.

Jeśli wykres ma ograniczoną liczbę skrzyżowań, można ją narysować z taką liczbą skrzyżowań w modelu polilinii (tj. Każda krawędź jest łańcuchem wielokątnym, o wiele bardziej powszechnym w literaturze do rysowania wykresów niż krzywe algebraiczne stopnia ograniczonego) z ograniczoną liczbą zagięć na krawędź. Jest to również bardziej ogólne, jeśli istnieje ograniczona liczba skrzyżowań na krawędź. Aby to zobaczyć, po prostu planuj wykres (zamień każde skrzyżowanie wierzchołkiem), a następnie zastosuj Fáry.

Teraz, aby użyć tego do odpowiedzi na twoje aktualne pytanie, musisz znaleźć krzywą algebraiczną, która jest arbitralnie zbliżona do danej polilinii, ze stopniem ograniczonym funkcją liczby zagięć polilinii. Można to również zrobić dość łatwo. Na przykład: dla każdego segmentu$s_i$ polilinii, niech $e_i$ być elipsą o wysokiej ekscentryczności, która jest bardzo blisko $s_i$, i pozwól $p_i$ być kwadratowym wielomianem, który jest dodatni na zewnątrz $e_i$ i negatywne w środku $e_i$. Niech twój ogólny wielomian przybierze formę$p=\epsilon-\prod_i p_i$ gdzie $\epsilon$jest małą dodatnią liczbą rzeczywistą. Następnie jeden składnik krzywej$p=0$będzie leżał trochę poza zjednoczeniem elips i może być użyty do zastąpienia polilinii; jego stopień będzie dwukrotnością liczby elips, która jest liniowa w liczbie przecięć na krawędź.

Jest to znane jako prostoliniowy numer przecięcia $\overline{\mathsf{cr}}(G)$, czyli minimalna liczba skrzyżowań między wszystkimi możliwymi rysunkami prostymi wykresu $G$. Porównaj z normalnym numerem przejścia$\mathsf{cr}(G)$, widać to $\overline{\mathsf{cr}}(G) \geq \mathsf{cr}(G)$. Twoje pytanie jest zasadniczo takie samo jak pytanie$\overline{\mathsf{cr}}(G) = \mathsf{cr}(G)$ gdyby $\mathsf{cr}(G) \leq k$ dla jakiejś stałej $k$.

W artykule Bounds dla prostoliniowych liczb przecięcia Bienstock i Dean to udowodnili

Twierdzenie. Gdyby$k \leq 3$, mamy $\overline{\mathsf{cr}}(G) = \mathsf{cr}(G)$. I dla$k \geq 4$, są wykresy $G_n$ z $\mathsf{cr}(G) = 4$ i $\overline{\mathsf{cr}}(G) \geq n$.

Zobacz ankietę na temat przekraczania liczb przez Richtera i Salazara w celach informacyjnych. Jeśli więc istnieje wariant twierdzenia Fáry'ego na wykresach z ograniczonymi liczbami przecinającymi, należy go ograniczyć$\mathsf{cr}(G) \leq 3$.

Na przykład z $\overline{\mathsf{cr}}(G) \neq \mathsf{cr}(G)$, rozważ pełny wykres na 8 wierzchołkach. To ma$\mathsf{cr}(K_8) = 18$ i $\overline{\mathsf{cr}}(K_8) = 19$.