Schemat łuku

Diagram łukowy wykresu Goldnera-Harary'ego . Ten wykres nie jest hamiltonowski, ale można go uczynić hamiltonowskim, dzieląc krawędź przecinaną przez czerwony segment linii przerywanej i dodając dwie krawędzie wzdłuż tego segmentu.

Diagram łukowy to styl rysowania wykresów , w którym wierzchołki wykresu są umieszczane wzdłuż linii w płaszczyźnie euklidesowej , a krawędzie są rysowane jako półkola w jednej lub obu półpłaszczyznach ograniczonych linią lub jako gładkie krzywe utworzone przez sekwencje półokręgów. W niektórych przypadkach odcinki samej linii są również dozwolone jako krawędzie, o ile łączą tylko kolejne wierzchołki wzdłuż linii. Odmiany tego stylu rysowania, w których półkola są zastępowane wypukłymi krzywymi innego typu, są również powszechnie nazywane diagramami łukowymi.

Użycie wyrażenia „diagram łukowy” dla tego rodzaju rysunków wynika z użycia podobnego typu diagramu przez Wattenberga (2002) do wizualizacji wzorców powtórzeń w strunach, za pomocą łuków do łączenia par równych podciągów. Jednak ten styl rysowania grafów jest znacznie starszy niż jego nazwa, sięga prac Saaty'ego (1964) i Nicholsona (1968) , którzy używali diagramów łukowych do badania przecinających się liczb grafów . Starszą, ale rzadziej używaną nazwą diagramów łukowych jest osadzenie liniowe . Niedawno diagramy łukowe były używane w ramach topologii obwodów węzłów i splotów, gdzie nazywane są schematami obwodów .

Heer, Bostock i Ogievetsky (2010) piszą, że diagramy łukowe „mogą nie oddawać ogólnej struktury wykresu tak skutecznie, jak układ dwuwymiarowy”, ale ich układ ułatwia wyświetlanie danych wielowymiarowych powiązanych z wierzchołkami grafu . Zastosowania diagramów łukowych obejmują diagram Fareya , wizualizację teoretycznych połączeń między liczbami wymiernymi oraz diagramy przedstawiające drugorzędową strukturę RNA, w których przecięcia diagramu reprezentują pseudowęzły w strukturze.

Wykresy planarne

Jak zauważył Nicholson (1968) , każdy rysunek wykresu na płaszczyźnie można zdeformować w diagram łukowy, nie zmieniając liczby jego przecięć. W szczególności każdy graf planarny ma planarny diagram łukowy. Jednak to osadzanie może wymagać użycia więcej niż jednego półkola dla niektórych jego krawędzi.

Jeśli wykres jest rysowany bez przecięć za pomocą diagramu łukowego, w którym każda krawędź jest pojedynczym półokręgiem, to rysunek jest dwustronicowym osadzeniem książki , co jest możliwe tylko dla grafów subhamiltonowskich , właściwego podzbioru grafów planarnych. Na przykład maksymalny graf planarny ma takie osadzenie wtedy i tylko wtedy, gdy zawiera cykl Hamiltona . Dlatego niehamiltonowski maksymalny planarny graf, taki jak wykres Goldnera-Harary'ego, nie może mieć płaskiego osadzania z jednym półkolem na krawędź. Testowanie, czy dany graf ma diagram łukowy bez przecięć tego typu (lub równoważnie, czy ma stronę numer dwa) jest NP-zupełne .

Jednak każdy graf planarny ma diagram łukowy, w którym każda krawędź jest narysowana jako biarc z co najwyżej dwoma półkolami. Co więcej, każdy graf skierowany na płaszczyźnie st ( wykres acykliczny skierowany na planar z jednym źródłem i jednym ujściem, oba na zewnętrznej powierzchni) ma diagram łukowy, w którym każda krawędź tworzy monotoniczną krzywą, przy czym wszystkie te krzywe są konsekwentnie zorientowane od jeden koniec linii wierzchołkowej w kierunku drugiego. W przypadku nieskierowanych wykresów planarnych jednym ze sposobów skonstruowania diagramu łukowego z co najwyżej dwoma półkolami na krawędź jest podzielenie wykresu i dodanie dodatkowych krawędzi, tak aby powstały wykres miał cykl Hamiltona ( i aby każda krawędź była podzielona co najwyżej raz), i użyć uporządkowania wierzchołków w cyklu Hamiltona jako uporządkowania wzdłuż linii. $potrzebne$ grafie planarnym z $wierzchołkami$ biarcze .

Minimalizacja skrzyżowań

Ponieważ NP-zupełne jest sprawdzenie, czy dany graf ma diagram łukowy z jednym półkolem na krawędź i bez przecięć, NP-trudne jest również znalezienie diagramu łukowego tego typu, który minimalizuje liczbę przecięć. Ten problem minimalizacji przecinania pozostaje NP-trudny dla grafów niepłaskich, nawet jeśli kolejność wierzchołków wzdłuż linii jest ustalona. Jednak w przypadku ustalonego porządku osadzenie bez przecięć (jeśli takie istnieje) można znaleźć w czasie wielomianowym, tłumacząc problem na problem spełnialności 2 , w którym zmienne reprezentują położenie każdego łuku, a ograniczenia zapobiegają przekraczaniu łuki przed umieszczeniem po tej samej stronie linii wierzchołków. Dodatkowo, w przypadku ustalonej kolejności, osadzenie minimalizujące skrzyżowania można przybliżyć , rozwiązując problem maksymalnego cięcia na wykresie pomocniczym, który reprezentuje półkola i ich potencjalne przecięcia (lub równoważnie, przybliżając wersję MAX2SAT instancji 2-spełnialności ).

Cimikowski i Shope (1996) , Cimikowski (2002) oraz He, Sýkora i Vrt'o (2005) omawiają heurystyki znajdowania diagramów łukowych z kilkoma skrzyżowaniami.

Orientacja zgodnie z ruchem wskazówek zegara

W przypadku rysowania grafów skierowanych powszechną konwencją jest rysowanie każdego łuku w kierunku zgodnym z ruchem wskazówek zegara, tak aby łuki skierowane od wcześniejszego do późniejszego wierzchołka w sekwencji były rysowane powyżej linii wierzchołków, a łuki skierowane od późniejszego do wcześniejsze wierzchołki są rysowane poniżej linii. Ta konwencja orientacji zgodnie z ruchem wskazówek zegara została opracowana jako część innego stylu rysowania wykresów przez Fekete i in. (2003) i zastosowane do diagramów łukowych przez Pretoriusa i van Wijka (2007) .

Aplikacje

Diagram Fareya

Diagram Fareya zbioru liczb wymiernych to struktura, którą można przedstawić geometrycznie jako diagram łukowy. W tej formie ma wierzchołek dla każdej liczby, umieszczony na osi liczbowej i półkolistą krawędź $r / s}$ linią łączącą pary liczb i $s {$ najprościej mówiąc) dla których ${\ Displaystyle | ps-rq | = 1}$ . Półkola diagramu można traktować jako linie w półpłaszczyznowym modelu Poincarégo płaszczyzny hiperbolicznej , z wierzchołkami umieszczonymi w nieskończonych punktach na linii granicznej tego modelu. Model półpłaszczyzny Poincarégo ma nieskończony punkt, który nie jest reprezentowany jako punkt na linii granicznej, wspólny punkt końcowy wszystkich promieni pionowych w modelu, i może być reprezentowany przez „ułamek” 1/0 (nieokreślony jako liczba ), z tą samą zasadą określania jego sąsiedztwa. Diagram Fareya dowolnego zbioru liczb wymiernych jest grafem planarnym, a diagram Fareya zbioru wszystkich liczb wymiernych tworzy teselację płaszczyzny hiperbolicznej za pomocą idealnych trójkątów .

Diagramy łukowe lub schematy obwodów są powszechnie stosowane w badaniu złożonych biopolimerów, takich jak białka i kwasy nukleinowe (DNA, RNA). Biopolimery są zwykle reprezentowane przez ich pierwszorzędową sekwencję monomerów wzdłuż linii diagramów i łuki powyżej linii reprezentujących wiązania między monomerami (np. aminokwasami w białkach lub zasadami w RNA lub DNA), które sąsiadują ze sobą w strukturze fizycznej polimeru pomimo tego, że nie sąsiadują ze sobą w kolejności sekwencji. Teoretyczne ramy topologii obwodów są następnie zwykle stosowane do wydobywania lokalnych i globalnych informacji topologicznych, które z kolei można powiązać z funkcją biologiczną zwiniętych cząsteczek. Gdy łuki się nie przecinają, układ dwóch łuków będzie równoległy (P) lub szeregowy (S). Kiedy występują skrzyżowania, reprezentują one to, co często nazywa się układem X w topologii obwodu. Statystyki P, S i X można wykorzystać do poznania kinetyki składania tych polimerów.

Diagramy łukowe zostały użyte przez Brandesa (1999) do wizualizacji diagramu stanu rejestru przesuwnego , przez Djidjeva i Vrt'o (2002) , aby pokazać, że liczba przecięć każdego wykresu jest dolna ograniczona przez kombinację jego szerokości cięcia i stopni wierzchołków przez Byrne'a i in. (2007) do wizualizacji interakcji między urządzeniami Bluetooth , a Owens i Jankun-Kelly (2013) do wizualizacji odległości zagrań w meczu futbolu amerykańskiego . Dodatkowe zastosowania tej techniki wizualizacji zostały omówione przez Nagel i Duval (2013) .

Notatki

•   Bekos, Michael A.; Kaufmann, Michael; Kobourov, Stephen G.; Symvonis, Antonios (2013), „Gładkie układy ortogonalne”, Graph Drawing: 20th International Symposium, GD 2012 , Redmond, WA, USA, 19–21 września 2012, poprawione wybrane artykuły , notatki z wykładów z informatyki, tom. 7704, Springer, s. 150–161, doi : 10.1007/978-3-642-36763-2_14 , ISBN 978-3-642-36762-5 .
• Bernhart, Frank R.; Kainen, Paul C. (1979), „Grubość książki wykresu”, Journal of Combinatorial Theory , seria B, 27 (3): 320–331, doi : 10.1016/0095-8956 (79) 90021-2 .
•   Brandes, Ulrik (1999), „Hunting down Graph B”, 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. 410–415, doi : 10.1007/3-540-46648-7_42 , ISBN 978-3-540-66904-3 .
• Byrne, Daragh; Lavelle, Barry; Jones, Gareth JF; Smeaton, Alan F. (2007), „Wizualizacja interakcji Bluetooth: łączenie diagramu łuku i technik DocuBurst” (PDF) , w: Ormerod, Thomas C.; Sas, Corina (red.), Proceedings of the 21st British HCI Group Annual Conference on HCI 2007: HCI… but not as we know it - Tom 2, BCS HCI 2007, University of Lancaster, Wielka Brytania, 3-7 września 2007 , Brytyjskie Towarzystwo Komputerowe, s. 129–132 .
•    kardynał Jean; Hoffmann, Michael; Kusters, Vincent; Tóth, Csaba D.; Wettstein, Manuel (2018), „Arc Diagramy, odległości klapki i triangulowanie Hamiltonian”, Computational Geometry , 68 : 206–225, Arxiv : 1611.02541 , doi : 10.1016/j.comgeo.2017.06.001 , MR 3715053 , S2CID 1169465.
• Chung, Fan RK ; Leightona, Franka Thompsona ; Rosenberg, Arnold L. (1987), „Osadzanie wykresów w książkach: problem z układem z aplikacjami do projektowania VLSI” (PDF) , SIAM Journal on Algebraic and Discrete Methods , 8 (1): 33–58, doi : 10.1137/0608002 .
•   Cimikowski, Robert (2002), „Algorithms for the fixed linear crossing number problem”, Discrete Applied Mathematics , 122 (1–3): 93–115, doi : 10.1016/S0166-218X (01) 00314-6 , MR 1907825 .
•   Cimikowski, Robert; Mumey, Brendan (2007), „Przybliżanie ustalonej liczby skrzyżowań liniowych”, Discrete Applied Mathematics , 155 (17): 2202–2210, doi : 10.1016/j.dam.2007.05.009 , MR 2360650 .
•   Cimikowski, Robert; Shope, Paul (1996), „Algorytm sieci neuronowej dla problemu z układem grafów”, IEEE Transactions on Neural Networks , 7 (2): 341–345, doi : 10.1109/72.485670 , PMID 18255588 .
•   Djidjev, Christo; Vrt'o, Imrich (2002), „Ulepszona dolna granica krzyżowania liczb”, Graph Drawing: 9th International Symposium, GD 2001 , Wiedeń, Austria, 23–26 września 2001, Revised Papers , Lecture Notes in Computer Science, tom . 2265, Springer, s. 96–101, doi : 10.1007/3-540-45848-4_8 , ISBN 978-3-540-43309-5 .
• Efrat, Alon; Erten, Cesim; Kobourov, Stephen G. (2007), „Rysunek łuku kołowego w stałej lokalizacji grafów planarnych”, Journal of Graph Algorithms and Applications , 11 (1): 145–164, doi : 10.7155 / jgaa.00140 .
• Fekete, Jean-Daniel; Wang, Dawid; Dang, Niem; Aris, Aleks; Plaisant, Catherine (2003), „Nakładanie linków do wykresów na mapach drzew”, IEEE Symp. w sprawie wizualizacji informacji, kompendium plakatów , s. 82–83 .
•   Gilman, Jane ; Keen, Linda (2002), „Sekwencje słów i numery przecięć” (PDF) , Złożone rozmaitości i geometria hiperboliczna (Guanajuato, 2001) , Współczesna matematyka, tom. 311, Providence, Rhode Island: American Mathematical Society, s. 231–249, doi : 10.1090/conm/311/05455 , MR 1940172 ; patrz sekcja 2.4, „Diagramy Fareya i ułamki ciągłe”
•   Giordano, Francesco; Liotta, Giuseppe; Miedzidze, Tamara; Symvonis, Antonios (2007), „Computing up topological book embeddings of up planar digraphs”, Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japonia, 17-19 grudnia 2007, Proceedings , Lecture Notes in Computer Science, tom . 4835, Springer, s. 172–183, doi : 10.1007/978-3-540-77120-3_17 , ISBN 978-3-540-77118-0 .
• On, Hongmei; Sýkora, Ondrej; Vrt'o, Imrich (2005), „Crossing Minimization Heuristics for 2-page Drawings” , Elektroniczne notatki w matematyce dyskretnej , 22 : 527–534, doi : 10.1016/j.endm.2005.06.088 .
• Hej, Jeffrey; Bostock, Michael; Ogievetsky, Vadim (2010), „Wycieczka po zoo wizualizacji”, Communications of the ACM , 53 (6): 59–67, doi : 10.1145/1743546.1743567 .
•    Kabakçıoğlu, A.; Stella, AL (listopad 2005), „Sieć pozbawiona skali ukryta w zapadającym się polimerze”, Physical Review E , 72 (5), 055102 (R), arXiv : cond-mat/0409584 , Bibcode : 2005PhRvE..72e5102K , doi : 10.1103/physreve.72.055102 , PMID 16383674 , S2CID 29977757
•   Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), „Minimalizacja przechodzenia w liniowych osadzaniach grafów”, IEEE Transactions on Computers , 39 (1): 124–127, doi : 10,1109/12,46286 , MR 1032144 .
• Nagel, Till; Duval, Erik (2013), „Wizualny przegląd diagramów łukowych” (PDF) , plakaty VIS 2013 , IEEE
•   Nicholson, TAJ (1968), „Procedura permutacji minimalizująca liczbę skrzyżowań w sieci”, Proceedings of the Institution of Electrical Engineers , 115 : 21–26, doi : 10.1049/piee.1968.0004 , MR 0311416 .
• Owensa, Seana Gabriela; Jankun-Kelly, TJ (2013), „Wizualizacje do eksploracji sezonu futbolu amerykańskiego i danych dotyczących gry” (PDF) , 1. IEEE VIS Workshop on Sports Data Visualization , IEEE
•    Pretorius, AJ; van Wijk, JJ (2007), „Pokonywanie luki semantycznej: wizualizacja wykresów przejść za pomocą diagramów zdefiniowanych przez użytkownika”, IEEE Computer Graphics and Applications , 27 (5): 58–66, doi : 10.1109/MCG.2007.121 , PMID 17913025 , S2CID 8643133 .
•     Saaty, Thomas L. (1964), „Minimalna liczba skrzyżowań w pełnych grafach”, Proceedings of the National Academy of Sciences of the United States of America , 52 (3): 688–690, Bibcode : 1964PNAS ... 52 ..688S , doi : 10.1073/pnas.52.3.688 , MR 0166772 , PMC 300329 , PMID 16591215 .
•    Wattenberg, M. (2002), „Diagramy łukowe: wizualizacja struktury w strunach”, Proc. Sympozjum IEEE na temat wizualizacji informacji (INFOVIS 2002) , s. 110–116, doi : 10.1109/INFVIS.2002.1173155 , ISBN 0-7695-1751-X , S2CID 881989 .