Dotykové grafy kružníc a Möbiove transformácie
Název práce v jazyce práce (slovenština): | Dotykové grafy kružníc a Möbiove transformácie |
---|---|
Název práce v češtině: | Dotykové grafy kružnic a Möbiovy transformace |
Název v anglickém jazyce: | Circle packing and Möbius transformations |
Klíčová slova: | geometrické reprezentácie grafov, circle packing, primal-dual circle packing, zložitosť, Möbiove transformácie |
Klíčová slova anglicky: | geometric representation of graphs, circle packing, primal-dual circle packing, computational complexity, Möbius transformations |
Akademický rok vypsání: | 2017/2018 |
Typ práce: | bakalářská práce |
Jazyk práce: | slovenština |
Ústav: | Katedra aplikované matematiky (32-KAM) |
Vedoucí / školitel: | Mgr. Peter Zeman |
Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 16.03.2018 |
Datum zadání: | 02.04.2018 |
Datum potvrzení stud. oddělením: | 01.06.2018 |
Datum a čas obhajoby: | 14.02.2019 10:00 |
Datum odevzdání elektronické podoby: | 03.01.2019 |
Datum odevzdání tištěné podoby: | 04.01.2019 |
Datum proběhlé obhajoby: | 14.02.2019 |
Oponenti: | prof. RNDr. Jan Kratochvíl, CSc. |
Zásady pro vypracování |
Študent/ka spracuje známe poznatky ohľadne dotykových grafov kružníc. Veta o dotykových grafoch kružníc (Circle packing theorem) hovorí, že graf je rovinný práve vtedy, keď je možné ho reprezentovať ako dotykový graf kružníc. Túto vetu dokázali nezávisle Koebe, Andreev a Thurston. Jedným z cieľov práce bude prehľadne spísať dôkaz tejto vety.
Ďalšia časť práce sa bude venovať algoritmom. Študent/ka prehľadne spíše popis algoritmu, ktorý v danej presnosti spočíta v polynomiálnom čase reprezentáciu rovinného grafu pomocou kružníc [1]. Dôležitý problém v oblasti geometrických reprezentácií grafov je testovať, či sa čiastočná reprezentácia dá rozšíriť. V prípade všeobecných dotykových grafov kružníc je tento problém NP-úplný [3]. Na druhú stranu, reprezentácia rovinnej triangulácie pomocou dotykov kružníc je jednoznačná, až na aplikáciu Möbiovej transformácie. Študent/ka sa zamyslí, či je v tomto prípade možné využiť poznatky komplexnej analýzy a poznatky ohľadne Möbiových transformácií k popisu polynomiálneho algoritmu na rozširovanie čiastočných reprezentácií [2]. |
Seznam odborné literatury |
[1] Mohar, Bojan. "A polynomial time circle packing algorithm." Discrete Mathematics 117.1-3 (1993): 257-263.
[2] Needham, Tristan. Visual complex analysis. Oxford University Press, 1998. [3] Chaplick, Steven, et al. "Contact representations of planar graphs: Extending a partial representation is hard." International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, Cham, 2014. |