Kör alakú elrendezés

A körkörös elrendezés egy olyan gráf-vizualizációs  stílus , amelyben a gráf csúcsai egy körben vannak elrendezve , gyakran egyenletes távolságra úgy, hogy egy szabályos sokszög csúcsait alkotják .

Alkalmazás

A kör alakú elrendezés jól alkalmazható hálózati kommunikációs topológiákhoz, például csillag vagy gyűrű [1] , valamint metabolikus hálózatok ciklikus részeihez [2] . Az ismert Hamilton-ciklusú gráfok esetében a kör alakú elrendezés lehetővé teszi, hogy a ciklust körként ábrázoljuk; egy ilyen kör alakú elrendezés képezi a Hamilton - köbös gráfok LCF-kódjának alapját [3] .

A körkörös elrendezés használható egy teljes gráf vizualizálására, de használható olyan töredékekhez is, mint a gráf csúcsok klaszterei, kétszeresen kapcsolódó komponensei [1] [4] , génklaszterek génkölcsönhatási gráfban [5] vagy természetes alcsoportok közösségi hálózat [6] . Több gráfcsúcsokkal rendelkező kört használva más klaszterezési módszerek is alkalmazhatók, például erővizualizációs algoritmusok [7] .

A körkörös elrendezés előnye olyan területeken, mint a bioinformatika vagy a közösségi hálózatok vizualizálása, a vizuális semlegességben rejlik [8]  – ha minden csúcs egyenlő távolságra van egymástól és a kép közepétől, akkor egyik csomópont sem foglal helyet. kiváltságos központosított pozíció. Ez azért fontos, mert van egy pszichológiai hajlam arra, hogy a központhoz közeli csomópontokat fontosabbnak tekintsék [9] .

Edge style

A gráfkép élei lehetnek körhúrok [10] , körívek [11] (esetleg a körre egy pontban merőlegesek, így a modell élei a hiperbolikus geometria Poincaré-modelljében egyenesekként vannak elrendezve ) ill. más típusú görbék [12] .

A kör belső és külső része közötti vizuális megkülönböztetés egy kör alakú elrendezésben felhasználható a kétféle élkép elkülönítésére. Például Gansner és Coren [12] körrajzi algoritmusa a körön belüli élek csoportosítását használja néhány csoporton kívüli éllel együtt [12] .

Szabályos gráfok körkörös elrendezése esetén a körön belül és kívül ívként húzott élekkel a beesési szögek (a pont érintőjével bezárt szög) az ív mindkét oldalán azonosak, ami leegyszerűsíti ábra szögfelbontásának optimalizálása [11] .

Átkelések száma

Egyes szerzők egy kör alakú elrendezés csúcsainak permutációjának megtalálásának problémáját tanulmányozzák, amely minimalizálja a metszéspontok számát, amikor az összes él a körön belül van megrajzolva. Ez a metszéspontszám csak a külső síkbeli gráfoknál nulla [10] [13] . Más gráfok esetében a megoldás generálása előtt külön-külön optimalizálható vagy redukálható az egyes kettős kapcsolatú gráfkomponensekre , mivel az ilyen komponensek anélkül rajzolhatók meg, hogy kölcsönhatásba lépnének egymással [13] .

Általánosságban elmondható, hogy a metszéspontok számának minimalizálása NP-teljes probléma [14] , de ez egy tényezővel közelíthető , ahol n egyenlő a csúcsok számával [15] . A komplexitás csökkentésére heurisztikus módszereket is kifejlesztettek, például jól átgondolt csúcsbeillesztési sorrenden és lokális optimalizáláson alapulókat [16] [1] [10] [17] [13] .

Egy kör alakú elrendezés is használható a kereszteződések számának maximalizálására. A csúcsok véletlenszerű permutációjának kiválasztása 1/3-os valószínűségű metszéspontot eredményez, így a metszéspontok várható száma háromszorosa lehet az összes lehetséges csúcshely közül a maximális metszésszámnak. Ennek a módszernek a derandomizálása olyan determinisztikus közelítő algoritmust ad , amelynek közelítési együtthatója három [18] .

Egyéb optimalitási kritériumok

A körelrendezés problémái közé tartozik továbbá a kör alakú elrendezés éleinek hosszának, a metszéspontok szögfelbontásának vagy a vágás szélességének optimalizálása (a köríveket az ellentétes ívekkel összekötő élek maximális száma) [16] [12] [19] [20] ; e problémák közül sok NP-teljes [16] .

Lásd még

Jegyzetek

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

Irodalom