Kruhové rozložení - Circular layout
v kreslení grafu, a kruhové rozložení je styl kreslení, který umisťuje vrcholy a graf na kruh, často rovnoměrně rozmístěné tak, aby tvořily vrcholy a pravidelný mnohoúhelník.
Aplikace
Kruhové rozložení je vhodné pro komunikaci topologie sítě jako hvězda nebo vyzváněcí sítě,[1] a pro cyklické části metabolické sítě.[2] Pro grafy se známým Hamiltonovský cyklus, kruhové rozložení umožňuje, aby byl cyklus zobrazen jako kruh, a tímto způsobem kruhové rozložení tvoří základ LCF notace pro Hamiltonian kubické grafy.[3]
Kruhové rozložení může být použito samostatně pro celý výkres grafu, ale také může být použito jako rozložení pro menší shluky vrcholů v rámci většího výkresu grafu, například jeho vzájemně propojené komponenty,[4] shluky geny v grafu genové interakce,[5] nebo přirozené podskupiny v rámci a sociální síť.[6] Pokud se tímto způsobem používá více kruhů vrcholů, používají se i jiné metody, jako např silově řízený graf lze použít k uspořádání klastrů.[7]
Jednou z výhod kruhového rozvržení v některých z těchto aplikací, jako je bioinformatika nebo vizualizace sociální sítě, je jeho neutralita:[8] umístěním všech vrcholů ve stejných vzdálenostech od sebe navzájem a od středu výkresu nedostává žádný privilegované postavení, což čelí tendenci diváků vnímat více důležitě uzly umístěné centrálněji.[9]
Styl hrany
Okraje výkresu mohou být zobrazeny jako akordy kruhu,[10] jako kruhové oblouky[11] (možná kolmo k vrcholovému kruhu, takže hrany modelují čáry Poincaré model disku z hyperbolická geometrie ), nebo jako jiné typy křivek.[12]
Vizuální rozlišení mezi vnitřkem a vnějškem vrcholového kruhu v kruhovém rozložení lze použít k oddělení dvou různých stylů kreslení hran. Například kruhový algoritmus kreslení Gansner & Koren (2007) používá seskupení hran v kruhu spolu s některými okraji, které nejsou seskupeny, nakreslené mimo kruh.[12]
Pro kruhové rozložení pravidelné grafy, s hranami nakreslenými uvnitř i vně jako kruhové oblouky, úhel dopadu jeden z těchto oblouků s vrcholem kruhu je stejný na obou koncích oblouku, což je vlastnost, která zjednodušuje optimalizaci úhlové rozlišení výkresu.[11]
Počet přejezdů
Několik autorů studovalo problém hledání a permutace vrcholů kruhového rozložení, které minimalizuje počet přechodů hran když jsou všechny hrany nakresleny uvnitř vrcholového kruhu. Tento počet přechodů je nulový pouze pro vnější rovinné grafy.[13] U ostatních grafů může být optimalizován nebo redukován samostatně pro každý vzájemně propojená součást grafu před kombinací řešení, protože tyto komponenty mohou být nakresleny tak, aby neinteragovaly.[14]
Obecně platí, že minimalizace počtu přejezdů je NP-kompletní,[15] ale lze je aproximovat poměrem přiblížení Ó(log2 n) kde n je počet vrcholů.[16] Byly také vyvinuty heuristické metody pro snížení složitosti přechodu, založené např. na pečlivém pořadí vkládání vrcholů a na lokální optimalizace.[17]
K maximalizaci počtu přechodů lze také použít kruhové rozložení. Zejména výběr a náhodná permutace protože vrcholy způsobí, že každé možné křížení nastane s pravděpodobností 1/3, takže očekávané číslo přechodů je faktorem tří z maximálního počtu přechodů mezi všemi možnými rozloženími. Derandomizace tato metoda dává a deterministický aproximační algoritmus s přibližný poměr tři.[18]
Další optimalizační kritéria
Spolu s přechody, kruhovými verzemi problémů s optimalizací délek hran v kruhovém rozložení, úhlovým rozlišením přechodů nebo šířka řezu (maximální počet hran, které spojují jeden oblouk kruhu s protilehlým obloukem), byly také brány v úvahu,[19] ale mnoho z těchto problémů je NP-kompletní.[20]
Viz také
- Akordový diagram, úzce související koncept ve vizualizaci informací
- Rovinnost, hádanka, ve které musí hráč přesunout vrcholy, aby rozmotal kresbu a rovinný graf, počínaje náhodným kruhovým rozvržením
Poznámky
- ^ Doğrusöz, Madden & Madden (1997).
- ^ Becker & Rojas (2001).
- ^ Pisanski a Servatius (2013).
- ^ Doğrusöz, Madden & Madden (1997); Six & Tollis (1999b).
- ^ Symeonidis & Tollis (2004).
- ^ Krebs (1996).
- ^ Doğrusöz, Belviranli & Dilek (2012).
- ^ Iragne a kol. (2005).
- ^ Huang, Hong & Eades (2007).
- ^ Six & Tollis (1999a).
- ^ A b Duncan a kol. (2012).
- ^ A b Gansner & Koren (2007).
- ^ Six & Tollis (1999a); Baur & Brandes (2005).
- ^ Baur & Brandes (2005).
- ^ Masuda a kol. (1987).
- ^ Shahrokhi a kol. (1995).
- ^ Mäkinen (1988); Doğrusöz, Madden & Madden (1997); Six & Tollis (1999a); On a Sýkora (2004); Baur & Brandes (2005).
- ^ Verbitsky (2008).
- ^ Mäkinen (1988); Gansner & Koren (2007); Nguyen a kol. (2011); Dehkordi a kol. (2013).
- ^ Mäkinen (1988).
Reference
- Baur, Michael; Brandes, Ulrik (2005), „Redukce křížení v kruhových rozloženích“, van van Leeuwen, Jan (ed.), Graficko-teoretické koncepty v informatice: 30. mezinárodní workshop, WG 2004, Bad Honnef, Německo, 21. – 23. Června 2004, revidované práce, Přednášky z informatiky, 3353, Springer, str. 332–343, doi:10.1007/978-3-540-30559-0_28.
- Becker, Moritz Y .; Rojas, Isabel (2001), „Algoritmus grafického uspořádání pro kreslení metabolických cest“, Bioinformatika, 17 (5): 461–467, doi:10.1093 / bioinformatika / 17.5.461, PMID 11331241.
- Dehkordi, Hooman Reisi; Nguyen, Quan; Eades, Peter; Hong, Seok-Hee (2013), „Kruhové grafy s velkými úhly křížení“, Algoritmy a výpočet: 7. mezinárodní workshop, WALCOM 2013, Kharagpur, Indie, 14. – 16. Února 2013, sborník, Přednášky v informatice, 7748, Springer, str. 298–309, doi:10.1007/978-3-642-36065-7_28.
- Doğrusöz, Uğur; Belviranli, M .; Dilek, A. (2012), „CiSE: Algoritmus rozvržení kruhové vložky pružiny“, Transakce IEEE na vizualizaci a počítačové grafice, 19 (6): 953–966, doi:10.1109 / TVCG.2012.178, hdl:11693/21006, PMID 23559509, S2CID 14365664.
- Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), „Kruhové rozložení v sadě nástrojů Grafické rozložení“, Grafická kresba: Symposium on Graph Drawing, GD '96, Berkeley, Kalifornie, USA, 18. – 20. Září 1996, sborník, Přednášky v informatice, 1190, Springer, str. 92–100, doi:10.1007/3-540-62495-3_40.
- Duncan, Christian A .; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G .; Nöllenburg, Martin (2012), „Lombardiho kresby grafů“, Journal of Graph Algorithms and Applications, 16 (1): 85–108, arXiv:1009.0579, doi:10,7155 / jgaa.00251.
- Gansner, Emden R .; Koren, Jehuda (2007), Kresba grafu: 14. mezinárodní sympozium, GD 2006, Karlsruhe, Německo, 18. – 20. Září 2006, revidované příspěvky, Přednášky v informatice, 4372, Springer, str. 386–398, doi:10.1007/978-3-540-70904-6_37.
- On, H .; Sýkora, Ondřej (2004), „Nové algoritmy kruhového kreslení“, Sborník seminářů o informačních technologiích - aplikace a teorie (ITAT), Slovensko, 15. – 19. Září.
- Huang, Weidong; Hong, Seok-Hee; Eades, Peter (2007), „Efekty konvence kreslení sociogramů a překročení hran ve vizualizaci sociální sítě“, Journal of Graph Algorithms and Applications, 11 (2): 397–429, doi:10,7155 / jgaa.00152.
- Iragne, Florian; Nikolski, Macha; Mathieu, Bertrand; Auber, David; Sherman, David (2005), „ProViz: vizualizace a zkoumání proteinové interakce“, Bioinformatika, 21 (2): 272–274, doi:10.1093 / bioinformatika / bth494, PMID 15347570.
- Krebs, Valdis (1996), „Vizualizace lidských sítí“ (PDF), Vydání 1.0: Měsíční zpráva Esther Dysonové, 2–96.
- Mäkinen, Erkki (1988), „Na kruhových rozloženích“, International Journal of Computer Mathematics, 24 (1): 29–37, doi:10.1080/00207168808803629.
- Masuda, S .; Kashiwabara, T .; Nakajima, K .; Fujisawa, T. (1987), „O NP-úplnosti problému s uspořádáním počítačové sítě“, Proceedings of the IEEE International Symposium on Circuits and Systems, str. 292–295. Jak uvádí Baur & Brandes (2005).
- Nguyen, Quan; Eades, Peter; Hong, Seok-Hee; Huang, Weidong (2011), „Velké úhly křížení v kruhových rozloženích“, Kreslení grafu: 18. mezinárodní sympozium, GD 2010, Konstanz, Německo, 21. – 24. Září 2010, revidované vybrané příspěvky, Přednášky v informatice, 6502, Springer, str. 397–399, doi:10.1007/978-3-642-18469-7_40.
- Pisanski, Tomaž; Servatius, Brigitte (2013), „2.3.2 Kubické grafy a LCF notace“, Konfigurace z grafického hlediska, Springer, str. 32, ISBN 9780817683641.
- Shahrokhi, Farhad; Sýkora, Ondřej; Székely, László A .; Vrt'o, Imrich (1995), „Vkládání knih a křížení čísel“, Graficko-teoretické koncepty v informatice: 20. mezinárodní workshop, WG '94, Herrsching, Německo, 16. – 18. Června 1994, sborník, Přednášky v informatice, 903, Springer, str. 256–268, doi:10.1007/3-540-59071-4_53.
- Šest, Janet M .; Tollis, Ioannis G. (1999a), „Kruhové výkresy biconnected grafů“, Algoritmické inženýrství a experimenty: Mezinárodní workshop ALENEX'99, Baltimore, MD, USA, 15. – 16. Ledna 1999, Vybrané příspěvky, Přednášky v informatice, 1619, Springer, str. 57–73, doi:10.1007 / 3-540-48518-X_4.
- Šest, Janet M .; Tollis, Ioannis G. (1999b), „Rámec pro kruhové výkresy sítí“, Kresba grafu: 7. mezinárodní sympozium, GD'99, hrad Štiřín, Česká republika, 15. – 19. Září 1999, sborník, Přednášky v informatice, 1731, Springer, str. 107–116, doi:10.1007/3-540-46648-7_11.
- Symeonidis, Alkiviadis; Tollis, Ioannis G. (2004), „Vizualizace biologických informací pomocí kruhových výkresů“, Analýza biologických a lékařských dat: 5. mezinárodní sympozium, ISBMDA 2004, Barcelona, Španělsko, 18. – 19. Listopadu 2004, sborník, Přednášky v informatice, 3337, Springer, str. 468–478, doi:10.1007/978-3-540-30547-7_47.
- Verbitsky, Oleg (2008), „O obfuskační složitosti planárních grafů“, Teoretická informatika, 396 (1–3): 294–300, arXiv:0705.3748, doi:10.1016 / j.tcs.2008.02.032, PAN 2412266, S2CID 5948167.