Aranjament circular

Aranjamentul circular este un  stil de vizualizare a unui grafic în care vârfurile unui grafic sunt aranjate pe un cerc , adesea uniform distanțate, astfel încât să formeze vârfurile unui poligon regulat .

Aplicație

Aranjamentul circular este foarte potrivit pentru topologiile de comunicații în rețea , cum ar fi stea sau inel [1] , precum și pentru părțile ciclice ale rețelelor metabolice [2] . Pentru graficele cu un ciclu hamiltonian cunoscut, aranjamentul circular permite ca ciclul să fie reprezentat ca un cerc; un astfel de aranjament circular formează baza pentru codul LCF al graficelor cubice hamiltoniene [3] .

Aranjamentul circular poate fi folosit pentru a vizualiza un grafic complet, dar poate fi folosit și pentru fragmente, cum ar fi clusterele de vârfuri ale graficului, componentele sale dublu conectate [1] [4] , clusterele de gene într-un grafic de interacțiune a genelor [5] , sau subgrupurile naturale din o rețea socială [ 6] . Folosind mai multe cercuri cu vârfuri de graf, pot fi aplicate și alte metode de grupare, cum ar fi algoritmii de vizualizare a forței [7] .

Avantajul unei aranjamente circulare în domenii precum bioinformatica sau vizualizarea rețelelor sociale constă în neutralitatea sa vizuală [8]  - când toate vârfurile sunt situate la o distanță egală unul de celălalt și de centrul imaginii, niciunul dintre noduri nu ocupă o poziție centralizată privilegiată. Acest lucru este important deoarece există o tendință psihologică de a percepe nodurile apropiate de centru ca fiind mai importante [9] .

Stilul marginii

Marginile dintr-o imagine grafică pot fi coarde de cerc [10] , arce de cerc [11] (eventual perpendiculare pe cerc într-un punct, astfel încât marginile modelului să fie dispuse ca linii drepte în modelul Poincaré al geometriei hiperbolice ) sau alte tipuri de curbe [12] .

Distincția vizuală dintre interiorul și exteriorul unui cerc într-un aranjament circular poate fi folosită pentru a separa cele două tipuri de imagini de margine. De exemplu, algoritmul de desenare a cercului al lui Gansner și Coren [12] folosește o grupare de muchii în interiorul cercului împreună cu unele muchii negrupate în afara cercului [12] .

Pentru o aranjare circulară a graficelor regulate cu muchiile desenate în interiorul și în afara cercului ca arce , unghiurile de incidență (unghiul cu tangenta la un punct) de pe ambele părți ale arcului sunt aceleași, ceea ce simplifică optimizarea rezoluției unghiulare a figurii [11] .

Numărul de treceri

Unii autori studiază problema găsirii unei permutări a vârfurilor unui aranjament circular care minimizează numărul de intersecții atunci când toate muchiile sunt desenate în interiorul cercului. Acest număr de intersecție este zero numai pentru graficele exterioare [10] [13] . Pentru alte grafice, acesta poate fi optimizat sau redus separat pentru fiecare componentă de graf biconectată înainte de a genera o soluție, deoarece astfel de componente pot fi desenate fără a interacționa între ele [13] .

În general, minimizarea numărului de intersecții este o problemă NP-completă [14] , dar poate fi aproximată printr-un factor , unde n este egal cu numărul de vârfuri [15] . Au fost dezvoltate și metode euristice pentru a reduce complexitatea, cum ar fi cele bazate pe o ordine bine gândită de inserare a nodurilor și pe optimizarea locală [16] [1] [10] [17] [13] .

Un aranjament circular poate fi folosit și pentru a maximiza numărul de intersecții. În special, alegerea unei permutări aleatorii a vârfurilor are ca rezultat o intersecție cu o probabilitate de 1/3, astfel încât numărul așteptat de intersecții poate fi de trei ori numărul maxim de intersecții dintre toate locațiile posibile ale vârfurilor. Derandomizarea acestei metode dă un algoritm de aproximare deterministă cu un coeficient de aproximare egal cu trei [18] .

Alte criterii de optimitate

De asemenea, problemele de aranjare circulară includ optimizarea lungimii muchiilor aranjamentului circular, rezoluția unghiulară a intersecțiilor sau lățimea tăieturii (numărul maxim de muchii care leagă arcurile de cerc cu cele opuse) [16] [12] [19] [20] ; multe dintre aceste probleme sunt NP-complete [16] .

Vezi și

Note

  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. ↑ El, Sýkora, 2004 .
  18. ↑ Verbitsky, 2008 .
  19. ↑ Nguyen, Eades, Hong, Huang, 2011 .
  20. ↑ Dehkordi, Nguyen, Eades, Hong, 2013 .

Literatură