Rysowanie wykresów ograniczonej liczby skrzyżowań

9

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.

arnab
źródło

Odpowiedzi:

12

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 segmentusi polilinii, niech ei być elipsą o wysokiej ekscentryczności, która jest bardzo blisko si, i pozwól pi być kwadratowym wielomianem, który jest dodatni na zewnątrz ei i negatywne w środku ei. Niech twój ogólny wielomian przybierze formęp=ϵipi gdzie ϵjest małą dodatnią liczbą rzeczywistą. Następnie jeden składnik krzywejp=0bę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ź.

David Eppstein
źródło
2
Dzięki. Czy istnieje przykład, który pokazuje, że generalnie nie można rysować przy minimalnej liczbie skrzyżowań przy użyciu krawędzi segmentów linii prostej?
arnab
@arnab: patrz odpowiedź Hsien-Chiha.
David Eppstein
12

Jest to znane jako prostoliniowy numer przecięcia cr¯(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

Twierdzenie. Gdybyk3, mamy cr¯(G)=cr(G). I dlak4, są wykresy Gn z cr(G)=4 i cr¯(G)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ćcr(G)3.

Na przykład z cr¯(G)cr(G), rozważ pełny wykres na 8 wierzchołkach. To macr(K8)=18 i cr¯(K8)=19.

Hsien-Chih Chang 張顯 之
źródło
Dzięki! To następnie odpowiada na pytanie zawarte w moim komentarzu do odpowiedzi Davida. Nadal chcę wiedzieć, czy moje oryginalne pytanie zostało zbadane.
arnab