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.
Jest to znane jako prostoliniowy numer przecięciacr¯¯¯¯(G) , czyli minimalna liczba skrzyżowań między wszystkimi możliwymi rysunkami prostymi wykresu G . Porównaj z normalnym numerem przejściacr(G) , widać to cr¯¯¯¯(G)≥cr(G) . Twoje pytanie jest zasadniczo takie samo jak pytaniecr¯¯¯¯(G)=cr(G) gdyby cr(G)≤k dla jakiejś stałej k .
W artykule Bounds dla prostoliniowych liczb przecięcia Bienstock i Dean to udowodnili
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ćcr(G)≤3 .
Na przykład zcr¯¯¯¯(G)≠cr(G) , rozważ pełny wykres na 8 wierzchołkach. To macr(K8)=18 i cr¯¯¯¯(K8)=19 .
źródło