Bågdiagram

Ett bågdiagram är en stil av grafrepresentation där hörnen är ordnade längs en rak linje på det euklidiska planet , och kanterna är ritade som halvcirklar på ett av de två halvplanen, eller som jämna kurvor som bildas av halvcirklarna. I vissa fall används linjesegment också för att representera grafkanter om de förbinder angränsande hörn på linjen.

Namnet "bågdiagram" för denna representation av grafer är en efterföljare till användningen av en liknande typ av Wattenberg-diagram [1] , som han använde för att visualisera upprepade fragment av linjer genom att koppla ihop par av identiska delsträngar. Men stilen för grafrepresentation i sig är mycket äldre än namnet och härstammar från Saaty [2] och Nicholson [3] , som använde bågdiagram för att studera skärningsantal av grafer . Ett äldre men mindre använt namn för bågdiagram är linjeinbäddning [4] .

Heer, Bostock och Ogiwetsky [5] skrev att bågdiagram "inte kan uttrycka den fullständiga strukturen av en graf lika effektivt som en tvådimensionell representation gör", men det gör det lättare att representera flerdimensionell data associerad med grafens hörn.

Plana grafer

Som Nicholson [3] noterade kan varje inbäddning av en graf i ett plan omvandlas till ett bågdiagram utan att ändra antalet skärningspunkter. I synnerhet har varje plan graf ett plan bågdiagram. Sådan kapsling kan dock kräva användning av mer än en halvcirkel för att rita några av grafens kanter.

Om en graf ritas utan bågkorsningar som ett bågdiagram där varje kant representeras av en enda halvcirkel, är ritningen en tvåsidig bokinbäddning , vilket endast är möjligt för sub-Hamiltonska grafer , en undergrupp av plana grafer [6 ] . Till exempel har en maximal plan graf sådan inbäddning om och bara om den innehåller en Hamiltonsk cykel . Således kan en icke-Hamiltonisk maximal plan graf som Goldner–Harari-grafen inte ha en plan inbäddning med en halvcirkel per kant. Att kontrollera om en given graf har ett bågdiagram utan skärningar av denna typ (eller, motsvarande, grafens boktjocklek är två) är ett NP-komplett problem [7] .

Men vilken plan graf som helst har ett bågdiagram där varje kant representeras som en bi -båge , bestående av högst två halvcirklar. Mer strikt, varje st -plan riktad graf (plan riktad acyklisk graf med en källa och en sänka, båda på utsidan) har ett bågdiagram där vilken kant som helst bildar en monoton kurva, alla kurvor (kanter) är riktade i samma riktning [8] . För oriktade plana grafer är ett sätt att konstruera ett bågdiagram med högst två halvcirklar per kant att dela grafen och lägga till fler kanter för att få en Hamiltonsk cykel (där kanterna är uppdelade i högst två delar), använd sedan ordningen längs Hamiltons cykel som ordningen för hörnen på en rät linje [9] .

Minimera korsningar

Eftersom att kontrollera om en given graf har ett bågdiagram utan skärningar med en halvcirkel per kant är ett NP-komplett problem, är det också ett NP-svårt problem att hitta ett bågdiagram som minimerar antalet skärningar. Problemet med att minimera antalet skärningar förblir NP-svårt för icke-plana grafer, även om ordningen på hörnen längs linjen redan är given [4] . Men i fallet med en given vertexordning kan en skärningsfri inbäddning (om en sådan finns) hittas i polynomtid genom att konvertera problemet till ett 2-tillfredsställelseproblem , där variablerna representerar platsen för varje båge , och begränsningar förhindrar att två korsande kanter ligger längs ena sidan av linjen med hörn [10] . Dessutom, i fallet med en fast placering av hörn, kan kapslingen med minimering av antalet skärningar approximeras genom att lösa problemet med maximal skärning i en hjälpgraf som representerar halvcirklar och deras potentiella skärningspunkter [11] .

Kimikowski, Shoup [12] [13] , He, Sikora och Wrto [14] diskuterade heuristiska algoritmer för att hitta bågdiagram med flera skärningspunkter.

Medurs orientering

För att representera riktade grafer är den allmänna konventionen att rikta bågarna medurs, så att vänster-till-höger-bågar ritas ovanför linjen, och höger-till-vänster-bågar ritas under linjen. Denna medurs orienteringskonvention utvecklades som en del av en annan stil av grafrepresentation av en grupp som inkluderade Fekete, Wang, Dang och Aris [15] , och Pretorius och van Wijk [16] tillämpade denna stil på bågdiagram .

Andra användningsområden

Bågdiagram användes av Brandes [17] för att visualisera skiftregistertillståndsdiagram , och av Jijev och Wrto [18] för att bevisa att skärningsnumret för någon graf är åtminstone lika med kvadraten på dess skärbredd.

Anteckningar

  1. ↑ Wattenberg, 2002 .
  2. ↑ Saaty, 1964 .
  3. ↑ 12 Nicholson , 1968 .
  4. ↑ 1 2 Masuda, Nakajima, Kashiwabara, Fujisawa, 1990 .
  5. ↑ Heer, Bostock, Ogievetsky, 2010 .
  6. ↑ Tillämpningen av halvcirklar för att rita kanter i bokkapsling användes redan av Bernhart och Kainen 1979 ( Bernhart, Kainen 1979 ), men den explicita associationen av bågdiagram med tvåsidiga häckningar verkar bero på Masuda, Nakajima, Kashiwabara, och Fujisawa ( Masuda, Nakajima, Kashiwabara, Fujisawa 1990 ).
  7. ↑ Chung, Leighton, Rosenberg, 1987 .
  8. ↑ Giordano, Liotta, Mchedlidze, Symvonis, 2007 .
  9. ↑ Bekos, Kaufmann, Kobourov, Symvonis, 2013 .
  10. ↑ Efrat, Erten, Kobourov, 2007 .
  11. ↑ Cimikowski, Mumey, 2007 .
  12. ↑ Cimikowski, Shope, 1996 .
  13. ↑ Cimikowski, 2002 .
  14. ↑ He, Sykora, Vrt'o, 2005 .
  15. ↑ Fekete, Wang, Dang, Aris, 2003 .
  16. ↑ Pretorius, van Wijk, 2007 .
  17. ↑ Brandes, 1999 .
  18. ↑ Djidjev, Vrt'o, 2002 .

Litteratur