Rozdzielczość kątowa (rysowanie wykresu)

Ten rysunek wykresu hipersześcianu ma rozdzielczość kątową π/4 .

W rysowaniu wykresów rozdzielczość kątowa rysunku wykresu jest najostrzejszym kątem utworzonym przez dowolne dwie krawędzie, które spotykają się we wspólnym wierzchołku rysunku.

Nieruchomości

Stosunek do stopnia wierzchołka

Formann i in. (1993) zaobserwowali, że każdy rysunek liniowy wykresu o maksymalnym stopniu d ma rozdzielczość kątową co najwyżej 2π/ d : jeśli v jest wierzchołkiem stopnia d , to krawędzie padające na v dzielą przestrzeń wokół v na d kliny z całkowity kąt 2π , a najmniejszy z tych klinów musi mieć kąt co najwyżej 2π/ d . Silniej, jeśli wykres jest d - regularny , musi mieć rozdzielczość kątową mniejszą niż $.$ to najlepsza rozdzielczość, jaką można osiągnąć dla wierzchołka na otoczce rysunku .

Związek z kolorowaniem wykresów

Jak Formann i in. (1993) wykazali, że największa możliwa rozdzielczość kątowa grafu G jest ściśle związana z liczbą chromatyczną kwadratu G ^{2 , grafu w tym samym zbiorze wierzchołków} , w którym pary wierzchołków są połączone krawędzią, ilekroć ich odległość w G wynosi najwyżej dwa. Jeśli G ² można pokolorować kolorami χ , to G można narysować z rozdzielczością kątową π/ χ − ε , dla dowolnego ε > 0 , przypisując różne kolory wierzchołkom regularnego χ -gonu i umieszczając każdy wierzchołek G blisko wierzchołka wielokąta o tym samym kolorze. Wykorzystując tę ​​konstrukcję wykazali, że każdy wykres o maksymalnym stopniu d ma rysunek o rozdzielczości kątowej proporcjonalnej do 1/ d ² . Ta granica jest bliska ścisłej: użyli metody probabilistycznej , aby udowodnić istnienie grafów o maksymalnym stopniu d , których wszystkie rysunki mają rozdzielczość kątową ${\ Displaystyle O \ lewo ({\ Frac {\ log d} {d ^ {2}}} \ prawej)}$ .

Istnienie optymalnych rysunków

Formann i in. (1993) podali przykład pokazujący, że istnieją grafy, które nie mają rysunku osiągającego maksymalną możliwą rozdzielczość kątową; zamiast tego wykresy te mają rodzinę rysunków, których rozdzielczości kątowe dążą do pewnej wartości granicznej, nie osiągając jej. W szczególności przedstawili 11-wierzchołkowy wykres, który zawiera rysunki o rozdzielczości kątowej π/3 - ε dla dowolnego ε > 0 , ale nie ma rysunku o rozdzielczości kątowej dokładnie π/3 .

Specjalne klasy grafów

Drzewa

Każde drzewo można narysować w taki sposób, że krawędzie są równomiernie rozmieszczone wokół każdego wierzchołka, co jest właściwością znaną jako doskonała rozdzielczość kątowa . Co więcej, jeśli krawędzie można dowolnie permutować wokół każdego wierzchołka, to taki rysunek jest możliwy, bez przecięć, ze wszystkimi krawędziami o długości jednostkowej lub większej i z całym rysunkiem mieszczącym się w ramce ograniczającej pole wielomianu . Jeśli jednak cykliczne uporządkowanie krawędzi wokół każdego wierzchołka jest już określone jako część danych wejściowych do problemu, wówczas osiągnięcie doskonałej rozdzielczości kątowej bez przecięć może czasami wymagać powierzchni wykładniczej.

Grafy zewnętrzne

Idealna rozdzielczość kątowa nie zawsze jest możliwa w przypadku grafów płaszczyzny zewnętrznej , ponieważ wierzchołki na wypukłym korpusie rysunku o stopniu większym niż jeden nie mogą mieć równo rozmieszczonych krawędzi padających wokół nich. Niemniej jednak każdy wykres na płaszczyźnie zewnętrznej o maksymalnym stopniu d ma rysunek na płaszczyźnie zewnętrznej z rozdzielczością kątową proporcjonalną do 1/ d .

Wykresy planarne

W przypadku grafów planarnych o maksymalnym stopniu d , technika kolorowania kwadratowego Formanna i in. (1993) dostarcza rysunek z rozdzielczością kątową proporcjonalną do 1/ d , ponieważ kwadrat grafu planarnego musi mieć liczbę chromatyczną proporcjonalną do d . Dokładniej, Wegner przypuszczał w 1977 r., że liczba chromatyczna kwadratu grafu planarnego wynosi co najwyżej ${\ Displaystyle \ max \ lewo (d + 5, {\ Frac {3d} {2}} + 1 \ prawej)}$ i wiadomo, że liczba chromatyczna wynosi co najwyżej ${\ styl wyświetlania {\ frac {5d} {3}} + O (1)}$ . Jednak rysunki wynikające z tej techniki na ogół nie są płaskie.

W przypadku niektórych wykresów planarnych optymalna rozdzielczość kątowa płaskiego rysunku liniowego wynosi O(1/ d ³ ) , gdzie d jest stopniem wykresu. Dodatkowo taki rysunek może być zmuszony do stosowania bardzo długich krawędzi, dłuższych wykładniczo niż najkrótsze krawędzie na rysunku. Malitz i Papakostas (1994) wykorzystali twierdzenie o upakowaniu okręgu i lemat o pierścieniu , aby pokazać, że każdy graf planarny o maksymalnym stopniu d ma planarny rysunek, którego rozdzielczość kątowa jest w najgorszym przypadku wykładniczą funkcją d , niezależną od liczby wierzchołków grafu.

Złożoność obliczeniowa

NP-trudne jest ustalenie, czy dany wykres maksymalnego stopnia d ma rysunek z rozdzielczością kątową 2π/ d , nawet w szczególnym przypadku, gdy d = 4 . Jednak w przypadku niektórych ograniczonych klas rysunków, w tym rysunków drzew, w których rozciągnięcie liści do nieskończoności tworzy wypukły podział płaszczyzny, jak również rysunków planarnych grafów, w których każda ograniczona ściana jest centralnie symetrycznym wielokątem, rysunek optymalnego rozdzielczość kątową można znaleźć w czasie wielomianowym .

Historia

Rozdzielczość kątowa została po raz pierwszy zdefiniowana przez Formanna i in. (1993) .

Chociaż pierwotnie zdefiniowano tylko dla prostych rysunków wykresów, późniejsi autorzy zbadali również rozdzielczość kątową rysunków, w których krawędzie są łańcuchami wielokątnymi, łukami kołowymi lub krzywymi splajnu.

Rozdzielczość kątowa wykresu jest ściśle związana z rozdzielczością przecięcia, czyli kątem utworzonym przez przecięcia na rysunku wykresu. W szczególności rysunek RAC ma na celu zapewnienie, że wszystkie te kąty są kątami prostymi , czyli największym możliwym kątem przecięcia.

Notatki

•   Brandes, Ulrik ; Szubina, Galina; Tamassia, Roberto (2000), „Poprawa rozdzielczości kątowej w wizualizacjach sieci geograficznych”, Data Visualization 2000: Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization w Amsterdamie, Holandia, 29-31 maja 2000 r. , doi : 10.1007/ 978-3-7091-6783-0_3 , ISBN 9783211835159 .
•   Carlson, Jozjasz; Eppstein, David (2007), „Drzewa o wypukłych ścianach i optymalnych kątach”, w: Kaufmann, Michael; Wagner, Dorothea (red.), Proc. 14. Int. Symp. Rysowanie wykresów (GD'06) , LNCS, tom. 4372, Springer-Verlag, s. 77–88, arXiv : cs.CG/0607113 , doi : 10.1007/978-3-540-70904-6_9 , S2CID 12598338 .
• Cheng, CC; Duncan, Kalifornia; Goodrich, MT ; Kobourov, SG (1999), „Rysowanie płaskich grafów za pomocą łuków kołowych”, Graph Drawing, 7. Międzynarodowe Sympozjum, GD'99, Zamek Štirín, Czechy 15–19 września 1999, Proceedings , Lecture Notes in Computer Science , tom. 1731, Springer-Verlag, s. 117–126, doi : 10.1007/3-540-46648-7_12 .
• Didimo, Walter; Eades, Piotr ; Liotta, Giuseppe (2009), „Rysowanie wykresów z przecięciami pod kątem prostym”, Algorytmy i struktury danych : 11. Międzynarodowe Sympozjum, WADS 2009, Banff, Kanada, 21-23 sierpnia 2009. Proceedings , Lecture Notes in Computer Science, tom. 5664, s. 206–217, doi : 10.1007/978-3-642-03367-4_19 .
• Duncan, Christian A.; Eppstein, David ; Goodrich, Michael T .; Kobourov, Stephen G.; Nöllenburg, Martin (2011), „Rysowanie drzew z doskonałą rozdzielczością kątową i obszarem wielomianu”, w: Brandes, Ulrik; Cornelsen, Sabine (red.), Proc. 18. Int. Symp. Rysowanie wykresów , notatki z wykładów z informatyki, tom. 6502, Springer-Verlag, s. 183–194, arXiv : 1009.0581 , doi : 10.1007/978-3-642-18469-7_17 .
•   Eppstein, D .; Wortman, K. (2011), „Optymalna rozdzielczość kątowa dla rysunków symetrycznych twarzy”, Journal of Graph Algorithms and Applications , 15 (4): 551–564, arXiv : 0907,5474 , doi : 10,7155/jgaa.00238 , S2CID 10356432 .
• Finkel, Benjamin; Tamassia, Roberto (2005), „Rysowanie wykresów krzywoliniowych metodą ukierunkowaną na siłę”, Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, 29 września - 2 października 2004, Revised Selected Papers, Lecture Notes w informatyce, tom. 3383, Springer-Verlag, s. 448–453, doi : 10.1007/978-3-540-31843-9_46 .
•   Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, FT ; Symvonis, A.; Welzl, E .; Woeginger, G. (1993), „Rysowanie wykresów w płaszczyźnie o wysokiej rozdzielczości”, SIAM Journal on Computing , 22 (5): 1035–1052, doi : 10.1137/0222063 , MR 1237161 .
• Garg, Ashim; Tamassia, Roberto (1994), „Rysunki planarne i rozdzielczość kątowa: algorytmy i granice”, Algorytmy, drugie doroczne sympozjum europejskie, Utrecht, Holandia, 26–28 września 1994, Proceedings , Lecture Notes in Computer Science, tom. 855, Springer-Verlag, s. 12–23, doi : 10.1007/BFb0049393 .
• Garg, Ashim; Tamassia, Roberto (1995), „O złożoności obliczeniowej testów planarności w górę i prostoliniowości”, w: Tamassia, Roberto; Tollis, Ioannis (red.), Rysowanie wykresów , notatki z wykładów z informatyki, tom. 894, Springer Berlin/Heidelberg, s. 286–297, doi : 10.1007/3-540-58950-3_384 .
•   Gutwenger, Carsten; Mutzel, Petra (1998), „Planarne rysunki polilinii o dobrej rozdzielczości kątowej”, Rysowanie wykresów (Montréal, QC, 1998) , Notatki z wykładów w Comput. Nauka, tom. 1547, Berlin: Springer, s. 167–182, doi : 10.1007/3-540-37623-2_13 , MR 1717450 .
• Halupczok, Immanuel; Schulz, André (2011), „Przypinanie balonów o doskonałych kątach i optymalnym obszarze”, Proceedings of the 19th International Symposium on Graph Drawing .
•   Kant, G. (1996), „Rysowanie grafów planarnych przy użyciu porządku kanonicznego”, Algorithmica , 16 (1): 4–32, doi : 10.1007/s004539900035 , hdl : 1874/16676 , MR 1394492 .
•   Kramer, Floryda; Kramer, Horst (2008), „Ankieta dotycząca kolorowania wykresów na odległość”, Matematyka dyskretna , 308 (2–3): 422–426, doi : 10.1016/j.disc.2006.11.059 , MR 2378044 .
•   Malitz, Seth; Papakostas, Achilleas (1994), „O rozdzielczości kątowej grafów planarnych”, SIAM Journal on Discrete Mathematics , 7 (2): 172–183, doi : 10.1137 / S0895480193242931 , MR 1271989 .
•   Molloy, Michael; Salavatipour, Mohammad R. (2005), „Ograniczenie liczby chromatycznej kwadratu płaskiego wykresu”, Journal of Combinatorial Theory , Seria B, 94 (2): 189–213, doi : 10.1016/j.jctb. 2004.12.005 , hdl : 1807/9473 , MR 2145512 .