Okrągły układ

Układ kołowy diagramu stanu dla protokołu bramy granicznej

Przyrostowa konstrukcja okrągłego układu dla modelu tworzenia sieci społecznościowej Barabásiego – Alberta

W rysowaniu wykresów układ kołowy to styl rysowania, który umieszcza wierzchołki wykresu na okręgu , często w równych odstępach , tak że tworzą wierzchołki regularnego wielokąta .

Aplikacje

Układy kołowe dobrze pasują do topologii sieci komunikacyjnych , takich jak sieci gwiazdowe lub pierścieniowe , oraz do cyklicznych części sieci metabolicznych . W przypadku wykresów ze znanym cyklem Hamiltona układ kołowy umożliwia przedstawienie cyklu jako koła iw ten sposób układy kołowe stanowią podstawę notacji LCF dla wykresów sześciennych Hamiltona .

Okrągły układ może być używany samodzielnie do całego rysunku grafu, ale może być również używany jako układ mniejszych klastrów wierzchołków w większym rysunku grafu, takich jak jego dwupołączone komponenty, klastry genów na wykresie interakcji genów, lub naturalne podgrupy w sieci społecznościowej . Jeśli w ten sposób używanych jest wiele okręgów wierzchołków, do rozmieszczenia klastrów można zastosować inne metody, takie jak rysowanie wykresów pod wpływem siły .

Jedną z zalet układu kołowego w niektórych z tych zastosowań, takich jak bioinformatyka lub wizualizacja sieci społecznościowych, jest jego neutralność: dzięki umieszczeniu wszystkich wierzchołków w równych odległościach od siebie i od środka rysunku żaden nie ma uprzywilejowanej pozycji, przeciwdziałając tendencja widzów do postrzegania bardziej centralnie położonych węzłów jako ważniejszych.

Styl krawędzi

Krawędzie rysunku można przedstawić jako cięciwy koła, łuki kołowe (ewentualnie prostopadłe do wierzchołka koła, tak że krawędzie modelują linie modelu dysku Poincarégo o geometrii hiperbolicznej ) lub jako inne typy krzywych.

Wizualne rozróżnienie między wewnętrzną i zewnętrzną stroną okręgu wierzchołków w układzie kołowym może służyć do oddzielenia dwóch różnych stylów rysowania krawędzi. Na przykład algorytm rysowania kołowego Gansnera i Korena (2007) wykorzystuje łączenie krawędzi w okręgu, wraz z niektórymi krawędziami, które nie są wiązane, rysowanymi poza okręgiem.

W przypadku układów kołowych grafów regularnych , z krawędziami narysowanymi zarówno wewnątrz, jak i na zewnątrz jako łuki kołowe , kąt padania jednego z tych łuków z okręgiem wierzchołków jest taki sam na obu końcach łuku, co upraszcza optymalizację kąta rozdzielczość rysunku.

Liczba przejść

Kilku autorów badało problem znalezienia permutacji wierzchołków układu kołowego, która minimalizuje liczbę przecięć krawędzi , gdy wszystkie krawędzie są narysowane wewnątrz koła wierzchołków. Ta liczba przecięć wynosi zero tylko dla grafów płaszczyzny zewnętrznej . W przypadku innych wykresów można go optymalizować lub redukować oddzielnie dla każdego dwupołączonego elementu wykresu przed połączeniem rozwiązań, ponieważ elementy te można narysować tak, aby nie wchodziły w interakcje.

Ogólnie rzecz biorąc, minimalizacja liczby skrzyżowań jest NP-zupełna , ale można ją przybliżyć współczynnikiem aproksymacji O (log ² n ), gdzie n jest liczbą wierzchołków. Opracowano również heurystyczne metody zmniejszania złożoności przecinania, oparte np. na starannej kolejności wstawiania wierzchołków i lokalnej optymalizacji .

Aby zmaksymalizować liczbę skrzyżowań, można również zastosować układ kołowy. W szczególności wybranie losowej permutacji dla wierzchołków powoduje, że każde możliwe skrzyżowanie wystąpi z prawdopodobieństwem 1/3, więc oczekiwana liczba skrzyżowań mieści się w zakresie trzykrotności maksymalnej liczby skrzyżowań wśród wszystkich możliwych układów. Derandomizacja tej metody daje algorytm aproksymacji deterministycznej o współczynniku aproksymacji trzy.

Inne kryteria optymalizacji

Obok przecięć pojawiły się również kołowe wersje problemów optymalizacji długości krawędzi w układzie kołowym, rozdzielczości kątowej przecięć czy szerokości cięcia ( maksymalnej liczby krawędzi łączących jeden łuk koła z łukiem przeciwległym). rozważane, ale wiele z tych problemów jest NP-zupełnych.

Zobacz też

Diagram akordów (wizualizacja informacji) , blisko spokrewniona koncepcja wizualizacji informacji
Planarność , łamigłówka, w której gracz musi przesuwać wierzchołki, aby rozplątać rysunek grafu planarnego , zaczynając od losowego układu kołowego

Linki zewnętrzne

Silnik układu kołowego Graphviz

Notatki

Baur, Michał; Brandes, Ulrik (2005), „Redukcja przekrojów w układach kołowych”, w: van Leeuwen, Jan (red.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Niemcy, 21-23 czerwca, 2004, poprawione artykuły , notatki z wykładów z informatyki , tom. 3353, Springer, s. 332–343, doi : 10.1007/978-3-540-30559-0_28 .
Becker, Moritz Y.; Rojas, Isabel (2001), „Algorytm układu wykresu do rysowania szlaków metabolicznych”, Bioinformatics , 17 (5): 461–467, doi : 10.1093/bioinformatics/17.5.461 , PMID 11331241 .
Dehkordi, Hooman Reisi; Nguyen, Quan; Eades, Piotr ; Hong, Seok-Hee (2013), „Rysunki wykresów kołowych z dużymi kątami przecięcia”, Algorytmy i obliczenia: 7th International Workshop, WALCOM 2013, Kharagpur, Indie, 14-16 lutego 2013 r., Proceedings , Lecture Notes in Computer Science, tom . 7748, Springer, s. 298–309, doi : 10.1007/978-3-642-36065-7_28 .
Doğrusöz, Uğur; Belviranli, M.; Dilek, A. (2012), „CiSE: algorytm układu osadzania kołowego sprężyny”, IEEE Transactions on Visualization and Computer Graphics , 19 (6): 953–966, doi : 10.1109/TVCG.2012.178 , hdl : 11693/21006 , PMID 23559509 , S2CID 14365664 .
Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), „Układ kołowy w zestawie narzędzi Graph Layout”, Graph Drawing: Symposium on Graph Drawing, GD '96, Berkeley, Kalifornia, USA, 18–20 września 1996, Proceedings , Lecture Notes in Computer Science, tom. 1190, Springer, s. 92–100, doi : 10.1007/3-540-62495-3_40 .
Duncan, Christian A.; Eppstein, David ; Goodrich, Michael T .; Kobourov, Stephen G.; Nöllenburg, Martin (2012), „Lombardiowe rysunki wykresów”, Journal of Graph Algorithms and Applications , 16 (1): 85–108, arXiv : 1009,0579 , doi : 10,7155/jgaa.00251 , S2CID 5000926 .
Gansner, Emden R.; Koren, Yehuda (2007), Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Niemcy, 18-20 września 2006, Revised Papers , Lecture Notes in Computer Science, tom. 4372, Springer, s. 386–398, doi : 10.1007/978-3-540-70904-6_37 .
On, H.; Sýkora, Ondrej (2004), „Nowe algorytmy rysowania kołowego”, Proceedings of the Workshop on Information Technologies - Applications and Theory (ITAT), Słowacja, 15-19 września .
Huang, Weidong; Hong, Seok-Hee ; Eades, Peter (2007), „Efekty konwencji rysowania socjogramu i przecinania krawędzi w wizualizacji sieci społecznościowych”, Journal of Graph Algorithms and Applications , 11 (2): 397–429, doi : 10.7155/jgaa.00152 .
Iragne, Florian; Nikolski, Macha; Mathieu, Bertrand; Auber, Dawid; Sherman, David (2005), „ProViz: wizualizacja i eksploracja interakcji białek”, Bioinformatics , 21 (2): 272–274, doi : 10.1093/bioinformatics/bth494 , PMID 15347570 .
Krebs, Valdis (1996), „Wizualizacja sieci ludzkich” (PDF) , wydanie 1.0: miesięczny raport Esther Dyson , 2–96 .
Mäkinen, Erkki (1988), „O układach kołowych”, International Journal of Computer Mathematics , 24 (1): 29–37, doi : 10.1080/00207168808803629 .
Masuda, S.; Kashiwabara, T.; Nakajima, K.; Fujisawa, T. (1987), „O NP-zupełności problemu układu sieci komputerowej”, Proceedings of the IEEE International Symposium on Circuits and Systems , s. 292–295 . Cytowane przez Baur & Brandes (2005) .
Nguyen, Quan; Eades, Piotr ; Hong, Seok-Hee ; Huang, Weidong (2011), „Duże kąty przecięcia w układach kołowych”, Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Niemcy, 21-24 września 2010, Revised Selected Papers , Lecture Notes in Computer Science, tom. 6502, Springer, s. 397–399, doi : 10.1007/978-3-642-18469-7_40 .
Pisanski, Tomaž ; Servatius, Brigitte (2013), „2.3.2 Wykresy sześcienne i notacja LCF”, Konfiguracje z graficznego punktu widzenia , Springer, s. 32, numer ISBN 9780817683641 .
Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (1995), „Osadzenia książek i liczby przecinające”, Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Niemcy, 16–18 czerwca 1994, Proceedings , Lecture Notes in Computer Nauka, tom. 903, Springer, s. 256–268, doi : 10.1007/3-540-59071-4_53 .
Sześć, Janet M.; Tollis, Ioannis G. (1999a), „Rysunki kołowe dwupołączonych grafów”, Algorithm Engineering and Experimentation: International Workshop ALENEX'99, Baltimore, MD, USA, 15–16 stycznia 1999, Selected Papers, Lecture Notes in Computer Science, tom. 1619, Springer, s. 57–73, doi : 10.1007/3-540-48518-X_4 .
Sześć, Janet M.; Tollis, Ioannis G. (1999b), „Rama dla kołowych rysunków sieci”, Graph Drawing: 7th International Symposium, GD'99, Zamek Štiřín, Czechy, 15–19 września 1999, Proceedings , Lecture Notes in Computer Science , tom. 1731, Springer, s. 107–116, doi : 10.1007/3-540-46648-7_11 .
Symeonidis, Alkiviadis; Tollis, Ioannis G. (2004), „Wizualizacja informacji biologicznych za pomocą okrągłych rysunków”, Biological and Medical Data Analysis: 5th International Symposium, ISBMDA 2004, Barcelona, Hiszpania, 18-19 listopada 2004, Proceedings , Lecture Notes in Computer Science , tom. 3337, Springer, s. 468–478, doi : 10.1007/978-3-540-30547-7_47 .
Verbitsky, Oleg (2008), „O złożoności zaciemniania grafów planarnych”, Theoretical Computer Science , 396 (1–3): 294–300, arXiv : 0705,3748 , doi : 10,1016/j.tcs.2008.02.032 , MR 2412266 , S2CID 5948167 .