Cirkulärt arrangemang

Cirkulärt arrangemang är en  grafvisualiseringsstil där hörn av en graf är ordnade på en cirkel , ofta jämnt fördelade, så att de bildar hörn av en vanlig polygon .

Applikation

Det cirkulära arrangemanget är väl lämpat för nätverkskommunikationstopologier såsom stjärna eller ring [1] såväl som för cykliska delar av metaboliska nätverk [2] . För grafer med en känd Hamilton-cykel tillåter det cirkulära arrangemanget att cykeln representeras som en cirkel; ett sådant cirkulärt arrangemang utgör grunden för LCF-koden för Hamiltonska kubiska grafer [3] .

Cirkulärt arrangemang kan användas för att visualisera en komplett graf, men kan också användas för fragment som grafvertexkluster, dess dubbelkopplade komponenter [1] [4] , genkluster i en geninteraktionsgraf [ 5] eller naturliga undergrupper i ett socialt nätverk [6] . Genom att använda flera cirklar med grafens hörn kan andra klustringsmetoder tillämpas, såsom kraftvisualiseringsalgoritmer [7] .

Fördelen med ett cirkulärt arrangemang inom områden som bioinformatik eller visualisering av sociala nätverk ligger i dess visuella neutralitet [8]  - när alla hörn är placerade på lika avstånd från varandra och från mitten av bilden, upptar ingen av noderna en privilegierad centraliserad position. Detta är viktigt eftersom det finns en psykologisk tendens att uppfatta noder nära centrum som viktigare [9] .

Kantstil

Kanterna i en grafbild kan vara cirkelackord [10] , cirkelbågar [ 11] (eventuellt vinkelräta mot cirkeln vid en punkt, så att modellens kanter är ordnade som raka linjer i Poincaré-modellen för hyperbolisk geometri ) eller andra typer av kurvor [12] .

Den visuella skillnaden mellan insidan och utsidan av en cirkel i ett cirkulärt arrangemang kan användas för att separera de två typerna av kantbilder. Till exempel använder Gansner och Corens [12] cirkelritningsalgoritm en gruppering av kanter inuti cirkeln tillsammans med några ogrupperade kanter utanför cirkeln [12] .

För ett cirkulärt arrangemang av reguljära grafer med kanter ritade inom och utanför cirkeln som bågar , är infallsvinklarna (vinkeln med tangenten i en punkt) på båda sidor av bågen desamma, vilket förenklar optimeringen av figurens vinkelupplösning [11] .

Antal korsningar

Vissa författare studerar problemet med att hitta en permutation av hörn i ett cirkulärt arrangemang som minimerar antalet skärningar när alla kanter är ritade inuti cirkeln. Detta skärningsnummer är noll endast för ytterplanära grafer [10] [13] . För andra grafer kan den optimeras eller reduceras separat för varje bikopplad grafkomponent innan en lösning genereras, eftersom sådana komponenter kan ritas utan att interagera med varandra [13] .

I allmänhet är att minimera antalet skärningar ett NP-komplett problem [14] , men det kan approximeras med en faktor , där n är lika med antalet hörn [15] . Heuristiska metoder har också utvecklats för att minska komplexiteten, såsom de som bygger på en genomtänkt vertexinsättningsordning och på lokal optimering [16] [1] [10] [17] [13] .

Ett cirkulärt arrangemang kan också användas för att maximera antalet korsningar. I synnerhet, att välja en slumpmässig permutation av hörnen resulterar i en skärning med en sannolikhet på 1/3, så det förväntade antalet skärningar kan vara tre gånger det maximala antalet skärningar bland alla möjliga hörnplatser. Avrandomisering av denna metod ger en deterministisk approximationsalgoritm med en approximationskoefficient lika med tre [18] .

Andra optimalitetskriterier

Problemen med cirkulärt arrangemang inkluderar också optimering av längden på kanterna på det cirkulära arrangemanget, vinkelupplösningen av korsningar eller snittets bredd (det maximala antalet kanter som förbinder de cirkulära bågarna med de motsatta) [16] [12] [19] [20] ; många av dessa problem är NP-kompletta [16] .

Se även

Anteckningar

  1. ↑ 1 2 3 Doğrusöz, Madden, Madden, 1997 .
  2. ↑ Becker, Rojas, 2001 .
  3. ↑ Pisanski, Servatius, 2013 .
  4. ↑ Six, Tollis, 1999b .
  5. ↑ Symeonidis, Tollis, 2004 .
  6. ↑ Krebs, 1996 .
  7. ↑ Doğrusöz, Belviranli, Dilek, 2012 .
  8. ↑ Iragne, Nikolski, Mathieu, Auber, Sherman, 2005 .
  9. ↑ Huang, Hong, Eades, 2007 .
  10. ↑ 1 2 3 Six, Tollis, 1999a .
  11. ↑ 1 2 Duncan, Eppstein, Goodrich, Kobourov, Nöllenburg, 2012 .
  12. ↑ 1 2 3 4 Gansner, Koren, 2007 .
  13. ↑ 1 2 3 Baur, Brandes, 2005 .
  14. ↑ Masuda, Kashiwabara, Nakajima, Fujisawa, 1987 .
  15. ↑ Shahrokhi, Sýkora, Székely, Vrt'o, 1995 .
  16. ↑ 1 2 3 Mäkinen, 1988 .
  17. ↑ He, Sykora, 2004 .
  18. ↑ Verbitsky, 2008 .
  19. ↑ Nguyen, Eades, Hong, Huang, 2011 .
  20. ↑ Dehkordi, Nguyen, Eades, Hong, 2013 .

Litteratur