Rysujesz wykresy z kilkoma „ostrymi” wierzchołkami?

15

W przypadku płaskiego osadzenia wykresu płaskiego na płaszczyźnie o prostych krawędziach, zdefiniuj wierzchołek jako ostry wierzchołek, jeśli maksymalny kąt między dwiema kolejnymi krawędziami wokół niego jest większy niż 180. Innymi słowy, jeśli istnieje linia przechodząca przez ten wierzchołek wierzchołek w osadzeniu, tak że wszystkie krawędzie padające na ten wierzchołek leżą po jednej stronie linii, wówczas wierzchołek jest „ostry”, w przeciwnym razie nie. Ponadto martwmy się tylko o wierzchołki o stopniu co najmniej 3.

Chcę narysować wykresy płaskie z kilkoma ostrymi wierzchołkami. Czy ktoś wcześniej studiował takie rysunki?

W szczególności chcę narysować wykresy płaskie o maksymalnym stopniu 3, tak aby liczba ostrych wierzchołków stopnia 3 w osadzeniu wynosiła a współrzędne wierzchołków można zapisać wielomianową liczbą bitów.O(log⁡n)

Oto, co mogę znaleźć po spędzeniu czasu w Google Scholar:

Moja miara ostrości wierzchołka jest związana z już zbadaną koncepcją zwaną rozdzielczością kątową . Z Wikipedii:

Rozdzielczość kątowa rysunku wykresu odnosi się do najostrzejszego kąta utworzonego przez dowolne dwie krawędzie, które spotykają się na wspólnym wierzchołku rysunku.

Zatem rysunek płaski z rozdzielczością kątową wokół wierzchołków stopnia 3 będzie odpowiedni dla mojego celu.π/2)

W przypadku wierzchołka o stopniu na rysunku rozdzielczość kątowa wokół niego może wynosić najwyżej .re2)π/re

Pytanie o to, czy to jest ścisłe, było badane w przeszłości, ale mogę znaleźć tylko asymptotyczne wyniki. Na przykład Malitz i Papakostas dowodzą, że każdy płaski wykres o maksymalnym stopniu można narysować z rozdzielczością kątową . Ale ten wynik nie daje dobrych granic dla przypadku, gdy .reαrere=3)

graph-theory cg.comp-geom graph-drawing Vinayak Pathak
źródło
2
Nie jestem pewien, co to oznacza. Jeśli narysujesz dowolny regularny wypukły wielokąt, maksymalny kąt wokół niego będzie większy niż 180. A zwykły wypukły wielokąt z dużym n jest dość daleki od „ostrego”.
Suresh Venkat
Definiuję ostrość jako właściwość wierzchołka, a nie całego rysunku. Jeśli więc dla wierzchołka można narysować linię prostą, tak że wszystkie krawędzie padające na ten wierzchołek leżą po jednej stronie linii prostej, wówczas wierzchołek jest „ostry”, w przeciwnym razie nie. Hmm, może powinienem napisać to w pierwotnym pytaniu.
Vinayak Pathak
@Vayayak: co z wierzchołkami o stopniu 1 i 2?
Marzio De Biasi
Można je zignorować.
Vinayak Pathak
Jeśli pożądana jest rozdzielczość kątowa, ma to sens, ponieważ patrząc na MINIMALNY kąt między sąsiednimi krawędziami. to zupełnie inne niż wcześniej zdefiniowane.
Suresh Venkat

Odpowiedzi:

13

Θ(n)

Z drugiej strony, jeśli potrzebujesz wyższych poziomów łączności, możesz uniknąć wielu ostrych wierzchołków. W szczególności, jeśli masz 3-połączony wykres płaski, można go narysować (np. Za pomocą twierdzenia Steinitza, aby znaleźć reprezentację wielościenną, a następnie uformować rzut perspektywiczny) w taki sposób, aby wszystkie ściany były wypukłe, co powoduje tylko zewnętrzna twarz powinna być ostra. Ale każdy 3-połączony wykres płaski można osadzić w taki sposób, że powierzchnia zewnętrzna ma co najwyżej pięć wierzchołków (najgorszym przypadkiem jest dwunastościan), dzięki czemu można narysować każdy 3-połączony wykres płaski (3-regularny lub nie) za pomocą większość pięciu ostrych wierzchołków.

David Eppstein
źródło