Bågdiagram

Ett bågdiagram av Goldner–Harary-grafen . Denna graf är inte Hamiltonsk, men kan göras Hamiltonsk genom att dela upp kanten som korsas av det röda streckade linjesegmentet och lägga till två kanter längs detta segment.

Ett bågdiagram är en stil av grafritning , där hörnen på en graf placeras längs en linje i det euklidiska planet , med kanter ritade som halvcirklar i ett eller båda av de två halvplanen som begränsas av linjen, eller som jämna kurvor bildas av sekvenser av halvcirklar. I vissa fall tillåts även linjesegment av själva linjen som kanter, så länge de bara förbinder hörn som är konsekutiva längs linjen. Variationer av denna ritstil där halvcirklarna ersätts av konvexa kurvor av någon annan typ kallas också vanligen för bågdiagram.

Användningen av frasen "bågdiagram" för denna typ av ritning följer användningen av en liknande typ av diagram av Wattenberg (2002) för att visualisera repetitionsmönstren i strängar, genom att använda bågar för att koppla ihop par av lika delsträngar. Denna stil av grafritning är dock mycket äldre än dess namn, och går tillbaka till Saatys (1964) och Nicholsons (1968) arbete, som använde bågdiagram för att studera korsande antal grafer . Ett äldre men mer sällan använt namn för bågdiagram är linjära inbäddningar . På senare tid har bågdiagram använts inom ramen för kretstopologi för knutar och härvor, där de kallas kretsdiagram .

Heer, Bostock & Ogievetsky (2010) skriver att bågdiagram "möjligen inte förmedlar den övergripande strukturen av grafen lika effektivt som en tvådimensionell layout", men att deras layout gör det enkelt att visa multivariat data associerad med grafens hörn . Tillämpningar av bågdiagram inkluderar Farey-diagrammet , en visualisering av talteoretiska kopplingar mellan rationella tal , och diagram som representerar RNA-sekundärstruktur där korsningarna av diagrammet representerar pseudoknoter i strukturen.

Plana grafer

Som Nicholson (1968) observerade kan varje ritning av en graf i planet deformeras till ett bågdiagram utan att ändra antalet korsningar. I synnerhet har varje plan graf ett plan bågdiagram. Den här inbäddningen kan dock behöva använda mer än en halvcirkel för vissa av dess kanter.

Om en graf ritas utan korsningar med hjälp av ett bågdiagram där varje kant är en enda halvcirkel, så är ritningen en tvåsidig bokinbäddning , något som bara är möjligt för de subhamiltonska graferna , en riktig delmängd av de plana graferna. Till exempel har en maximal plan graf en sådan inbäddning om och endast om den innehåller en Hamiltonsk cykel . Därför kan en icke-Hamiltonisk maximal plan graf som Goldner–Harary-grafen inte ha en plan inbäddning med en halvcirkel per kant. Att testa om en given graf har ett korsningsfritt bågdiagram av denna typ (eller motsvarande, om den har sidnummer två) är NP-komplett .

Varje plan graf har dock ett bågdiagram där varje kant är ritad som en bibåge med högst två halvcirklar. Mer starkt, varje st -plan riktad graf (en plan riktad acyklisk graf med en enda källa och en enda sänka, båda på utsidan) har ett bågdiagram där varje kant bildar en monoton kurva, med alla dessa kurvor konsekvent orienterade från ena änden av vertexlinjen mot den andra. För oriktade plana grafer är ett sätt att konstruera ett bågdiagram med högst två halvcirklar per kant att dela upp grafen och lägga till extra kanter så att den resulterande grafen har en Hamiltonsk cykel (och så att varje kant delas upp högst en gång ) , och att använda ordningen av hörnen på Hamiltons cykel som ordningen längs linjen. I en plan graf med ${\displaystyle n} hörn$ behövs högst ${\displaystyle n/2} biarcs.$

Minimera korsningar

Eftersom det är NP-komplett att testa om en given graf har ett bågdiagram med en halvcirkel per kant och inga korsningar, är det också NP- svårt att hitta ett bågdiagram av denna typ som minimerar antalet korsningar. Detta korsningsminimeringsproblem förblir NP-hårt, för icke-plana grafer, även om ordningen av hörnen längs linjen är fixerad. Men i fallet med fast ordning kan en inbäddning utan korsningar (om sådana finns) hittas i polynomtid genom att översätta problemet till ett problem med 2- tillfredsställelse , där variablerna representerar placeringen av varje båge och begränsningarna förhindrar korsning bågar från att placeras på samma sida av vertexlinjen. Dessutom, i fallet med fast ordning, kan en korsningsminimerande inbäddning approximeras genom att lösa ett maximalt skärproblem i en hjälpgraf som representerar halvcirklarna och deras potentiella korsningar (eller motsvarande, genom att approximera MAX2SAT-versionen av instansen med 2-tillfredsställelse ).

Cimikowski & Shope (1996) , Cimikowski (2002) och He, Sýkora & Vrt'o (2005) diskuterar heuristik för att hitta bågdiagram med få korsningar.

Medurs orientering

För ritningar av riktade grafer är en vanlig konvention att rita varje båge i medurs riktning, så att bågar som är riktade från ett tidigare till ett senare hörn i sekvensen ritas ovanför vertexlinjen och bågar riktade från ett senare till ett senare hörn. tidigare vertex ritas under linjen. Denna medurs orienteringskonvention utvecklades som en del av en annan grafritningsstil av Fekete et al. (2003) , och tillämpas på bågdiagram av Pretorius & van Wijk (2007) .

Ansökningar

Ett Farey-diagram

Farey -diagrammet för en uppsättning rationella tal är en struktur som kan representeras geometriskt som ett bågdiagram. I den här formen har den en vertex för varje tal, placerad på tallinjen , och en halvcirkelformad kant ovanför linjen som förbinder par av tal $p/q$ och $r/s$ ( i enklaste termer) för vilka $|ps-rq|=1$ . Halvcirklarna i diagrammet kan ses som linjer i Poincarés halvplansmodell av det hyperboliska planet , med hörn placerade vid oändliga punkter på gränslinjen för denna modell. Poincarés halvplansmodell har en oändlig punkt som inte representeras som punkt på gränslinjen, den delade ändpunkten för alla vertikala strålar i modellen, och denna kan representeras av "fraktionen" 1/0 (odefinierat som ett tal ), med samma regel för att bestämma dess närhet. Farey-diagrammet för en uppsättning rationella tal är en plan graf, och Farey-diagrammet för uppsättningen av alla rationella tal bildar en tessellation av det hyperboliska planet med ideala trianglar .

Bågdiagram eller kretsdiagram används ofta för att studera vikta biopolymerer som proteiner och nukleinsyror (DNA, RNA). Biopolymerer representeras typiskt av sin primära monomersekvens längs linjen i diagrammen och med bågar ovanför linjen som representerar bindningar mellan monomerer (t.ex. aminosyror i proteiner eller baser i RNA eller DNA) som ligger intill i polymerens fysiska struktur trots att den inte är intilliggande i sekvensordningen. Det teoretiska ramverket för kretstopologi används sedan typiskt för att extrahera lokal och global topologisk information, som i sin tur kan relateras till den biologiska funktionen hos de vikta molekylerna. När bågar inte korsar varandra kommer arrangemanget av de två bågarna att vara antingen parallella (P) eller serier (S). När det finns korsningar representerar korsningarna vad som ofta kallas X-arrangemang i kretstopologi. Statistiken för P, S och X kan användas för att lära sig om vikningskinetiken för dessa polymerer.

Bågdiagram användes av Brandes (1999) för att visualisera tillståndsdiagrammet för ett skiftregister , av Djidjev & Vrt'o (2002) för att visa att korsningstalet för varje graf är lägre avgränsat av en kombination av dess skärbredd och vertexgrader av Byrne et al. (2007) för att visualisera interaktioner mellan Bluetooth- enheter, och av Owens & Jankun-Kelly (2013) för att visualisera mängden pjäser i en omgång amerikansk fotboll . Ytterligare tillämpningar av denna visualiseringsteknik kartläggs av Nagel & Duval (2013) .

Anteckningar

•   Bekos, Michael A.; Kaufmann, Michael; Kobourov, Stephen G.; Symvonis, Antonios (2013), "Smooth ortogonal layouts", Graph Drawing: 20th International Symposium, GD 2012 , Redmond, WA, USA, 19–21 september 2012, Revised Selected Papers , Lecture Notes in Computer Science, vol. 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), "The book thickness of a graph", Journal of Combinatorial Theory , Series 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 , Štiřín Castle, Tjeckien 15–19 september 1999, Proceedings , Lecture Notes in Computer Science, vol. 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), "Visualisera Bluetooth-interaktioner: att kombinera bågdiagrammet och DocuBurst-tekniker" ( PDF) , i 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 - Volym 2, BCS HCI 2007, University of Lancaster, Storbritannien, 3-7 september 2007 , British Computer Society, s. 129–132 .
• kardinal, Jean; Hoffmann, Michael; Kusters, Vincent; Tóth, Csaba D.; Wettstein, Manuel (2018), "Arc diagrams, flip distances, and Hamiltonian triangulations", Computational Geometry , 68 : 206–225 , arXiv : 1611.02541 , doi : 10.1016 / j.comgeo.2017 169465   
• Chung, Fan RK ; Leighton, Frank Thompson ; Rosenberg, Arnold L. (1987), "Embedding graphs in books: A layout problem with applications to VLSI design" (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 5228 1907 .
•   Cimikowski, Robert; Mumey, Brendan (2007), "Approximating the fixed linear crossing number", Discrete Applied Mathematics , 155 (17): 2202–2210, doi : 10.1016/j.dam.2007.05.009 , MR 2360650 .
•   Cimikowski, Robert; Shope, Paul (1996), "A neural-network algorithm for a graph layout problem", IEEE Transactions on Neural Networks , 7 (2): 341–345, doi : 10.1109/72.485670 , PMID 18255588 .
•   Djidjev, Hristo; Vrt'o, Imrich (2002), "An improved lower bound for crossing numbers", Graph Drawing: 9th International Symposium, GD 2001 , Wien, Österrike, 23–26 september 2001, Revised Papers , Lecture Notes in Computer Science, vol. . 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), "Fixed-location circular arc drawing of planar graphs", Journal of Graph Algorithms and Applications , 11 (1): 145–164, doi : 10.7155/jgaa.00140 .
• Fekete, Jean-Daniel; Wang, David; Dang, Niem; Aris, Aleks; Plaisant, Catherine (2003), "Överlägga graflänkar på trädkartor", IEEE Symp. om informationsvisualisering, affischkompendium , s. 82–83 .
•   Gilman, Jane ; Keen, Linda (2002), "Ordsekvenser och korsningsnummer" (PDF) , Komplexa grenrör och hyperbolisk geometri (Guanajuato, 2001) , Contemporary Mathematics, vol. 311, Providence, Rhode Island: American Mathematical Society, s. 231–249, doi : 10.1090/conm/311/05455 , MR 1940172 ; se avsnitt 2.4, "Farey-diagram och fortsatta fraktioner"
•   Giordano, Francesco; Liotta, Giuseppe; Mchedlidze, Tamara; Symvonis, Antonios (2007), "Computing upward topological book embeddings of upward planar digraphs", Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, 17-19 december 2007, Proceedings , Lecture Notes in Computer Science, vol. . 4835, Springer, s. 172–183, doi : 10.1007/978-3-540-77120-3_17 , ISBN 978-3-540-77118-0 .
• Han, Hongmei; Sykora, Ondrej; Vrt'o, Imrich (2005), "Crossing Minimization Heuristics for 2-page Drawings" , Electronic Notes in Discrete Mathematics , 22 : 527–534, doi : 10.1016/j.endm.2005.06.088 .
• Heer, Jeffrey; Bostock, Michael; Ogievetsky, Vadim (2010), "A tour through the visualization zoo", Communications of the ACM , 53 (6): 59–67, doi : 10.1145/1743546.1743567 .
•    Kabakçıoğlu, A.; Stella, AL (november 2005), "Scale-free network hidden in a collapsing polymer", Physical Review E , 72 (5), 055102(R), arXiv : cond-mat/0409584 , Bibcode : 2005PhRvE..72e5102K , doii : 10.1103/physreve.72.055102 , PMID 16383674 , S2CID 29977757
•   Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Crossing minimization in linear embeddings of graphs", IEEE Transactions on Computers , 39 (1): 124–127, doi : 10.1109/12.46286 , MR 1032144 .
• Nagel, Till; Duval, Erik (2013), "A visual survey of arc diagrams" (PDF) , VIS Posters 2013 , IEEE
•   Nicholson, TAJ (1968), "Permutationsprocedur för att minimera antalet korsningar i ett nätverk", Proceedings of the Institution of Electrical Engineers , 115 : 21–26, doi : 10.1049/piee.1968.0004 , MR 0311416 .
• Owens, Sean Gabriel; Jankun-Kelly, TJ (2013), "Visualiseringar för utforskning av amerikansk fotbollssäsong och speldata" ( PDF) , 1st IEEE VIS Workshop on Sports Data Visualization , IEEE
•    Pretorius, AJ; van Wijk, JJ (2007), "Bridging the semantic gap: Visualizing transition graphs with user-defined diagrams", IEEE Computer Graphics and Applications , 27 (5): 58–66, doi : 10.1109/MCG.2007.121 , PMID 15791300 S2CID 8643133 .
•     Saaty, Thomas L. (1964), "Minsta antal korsningar i kompletta grafer", 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), "Arc diagrams: visualizing structure in strings", Proc. IEEE Symposium o nInformation Visualization (INFOVIS 2002) , s. 110–116, doi : 10.1109/INFVIS.2002.1173155 , ISBN 0-7695-1751-X , S2CID 881989 .