Kruhové uspořádání

Kruhové uspořádání je  styl vizualizace grafu , ve kterém jsou vrcholy grafu uspořádány na kružnici , často rovnoměrně rozmístěné, takže tvoří vrcholy pravidelného mnohoúhelníku .

Aplikace

Kruhové uspořádání se dobře hodí pro topologie síťové komunikace jako hvězda nebo prstenec [1] i pro cyklické části metabolických sítí [2] . Pro grafy se známým Hamiltonovským cyklem umožňuje kruhové uspořádání, aby byl cyklus reprezentován jako kruh; takové kruhové uspořádání tvoří základ pro LCF kód hamiltonovských kubických grafů [3] .

Kruhové uspořádání lze použít k vizualizaci kompletního grafu, ale lze jej použít i pro fragmenty, jako jsou shluky vrcholů grafu, jeho dvojitě spojené komponenty [1] [4] , shluky genů v grafu interakce genů [5] , nebo přirozené podskupiny v sociální síť [ 6] . Pomocí více kružnic s vrcholy grafu lze použít další metody shlukování, jako jsou algoritmy vizualizace síly [7] .

Výhoda kruhového uspořádání v oborech jako je bioinformatika nebo vizualizace sociálních sítí spočívá v jeho vizuální neutralitě [8]  - když jsou všechny vrcholy umístěny ve stejné vzdálenosti od sebe i od středu obrázku, žádný z uzlů nezabírá privilegované centralizované postavení. To je důležité, protože existuje psychologická tendence vnímat uzly blízko středu jako důležitější [9] .

Styl okraje

Hrany v obrázku grafu mohou být kruhové tětivy [10] , kruhové oblouky [11] (případně kolmé na kružnici v bodě, takže hrany modelu jsou v Poincarého modelu hyperbolické geometrie uspořádány jako přímky ) nebo jiné typy křivek [12] .

Vizuální rozlišení mezi vnitřkem a vnějškem kruhu v kruhovém uspořádání lze použít k oddělení dvou typů okrajových obrazů. Například algoritmus kreslení kruhu Gansnera a Corena [12] používá seskupení hran uvnitř kruhu spolu s některými neseskupenými hranami vně kruhu [12] .

Pro kruhové uspořádání pravidelných grafů s hranami nakreslenými uvnitř a vně kruhu jako oblouky , jsou úhly dopadu (úhel s tečnou v bodě) na obou stranách oblouku stejné, což zjednodušuje optimalizace úhlového rozlišení obrázku [11] .

Počet přejezdů

Někteří autoři studují problém nalezení permutace vrcholů kruhového uspořádání, která minimalizuje počet průsečíků , když jsou všechny hrany nakresleny uvnitř kruhu. Toto číslo průsečíku je nulové pouze u vnějších rovinných grafů [10] [13] . U jiných grafů lze před generováním řešení optimalizovat nebo redukovat samostatně pro každou bipropojenou komponentu grafu, protože takové komponenty lze kreslit bez vzájemné interakce [13] .

Obecně platí, že minimalizace počtu průsečíků je NP-úplný problém [14] , ale lze jej aproximovat faktorem , kde n je rovno počtu vrcholů [15] . Ke snížení složitosti byly vyvinuty také heuristické metody, jako jsou ty založené na dobře promyšleném pořadí vkládání vrcholů a na lokální optimalizaci [16] [1] [10] [17] [13] .

Pro maximalizaci počtu průsečíků lze také použít kruhové uspořádání. Zejména výběr náhodné permutace vrcholů vede k průniku s pravděpodobností 1/3, takže očekávaný počet průsečíků může být trojnásobkem maximálního počtu průsečíků mezi všemi možnými umístěními vrcholů. Derandomizace této metody poskytuje deterministický aproximační algoritmus s aproximačním koeficientem rovným třem [18] .

Další kritéria optimality

Mezi problémy kruhového uspořádání patří také optimalizace délky hran kruhového uspořádání, úhlové rozlišení průsečíků nebo šířka řezu (maximální počet hran, které spojují kruhové oblouky s protilehlými) [16] [12] [19] [20] ; mnohé z těchto problémů jsou NP-úplné [16] .

Viz také

Poznámky

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

Literatura