Dotykové grafy kružníc a Möbiove transformácie
| Thesis title in thesis language (Slovak): | Dotykové grafy kružníc a Möbiove transformácie |
|---|---|
| Thesis title in Czech: | Dotykové grafy kružnic a Möbiovy transformace |
| Thesis title in English: | Circle packing and Möbius transformations |
| Key words: | geometrické reprezentácie grafov, circle packing, primal-dual circle packing, zložitosť, Möbiove transformácie |
| English key words: | geometric representation of graphs, circle packing, primal-dual circle packing, computational complexity, Möbius transformations |
| Academic year of topic announcement: | 2017/2018 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | slovenština |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | Mgr. Peter Zeman |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 16.03.2018 |
| Date of assignment: | 02.04.2018 |
| Confirmed by Study dept. on: | 01.06.2018 |
| Date and time of defence: | 14.02.2019 10:00 |
| Date of electronic submission: | 03.01.2019 |
| Date of submission of printed version: | 04.01.2019 |
| Date of proceeded defence: | 14.02.2019 |
| Opponents: | prof. RNDr. Jan Kratochvíl, CSc. |
| Guidelines |
| Š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]. |
| References |
| [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. |