Praktické kreslení grafů pro teorii grafů
| Název práce v češtině: | Praktické kreslení grafů pro teorii grafů |
|---|---|
| Název v anglickém jazyce: | Practical graph drawing for graph theory |
| Klíčová slova: | kreslení grafů, struktura |
| Klíčová slova anglicky: | graph drawing, structure |
| Akademický rok vypsání: | 2019/2020 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | doc. Mgr. Robert Šámal, Ph.D. |
| Řešitel: |
| Zásady pro vypracování |
| Úkolem řešitele bude prozkoumat stávající algoritmy pro kreslení grafů
a tyto algoritmy vylepšit. Zaměření bude na grafy, které může chtít vykreslit výzkumník v teorii grafů -- obvykle nerovinné, s několika desítkami vrcholů. Cílem je najít nakreslení, které je pěkné, přehledné, a případně znázorňuje nějakou strukturu zadaného grafu. Navrhované varianty: -- vylepšené heuristiky pro názorné vykreslení nerovinných grafů (kupř. hrany nejsou nakresleny blízko vrcholům, které na nich neleží, vrcholy neleží blízko sebe, atd.) -- znázornění struktury grafu: symetrie, zadaný rozklad, atd. -- další dle uvážení studenta a postupu prací Vedle teoretického rozboru student navržené postupy implementuje a provede srovnání s jinými balíčky pro kreslení grafů (např. [1-4]). Implementace bude v prostředí Sage [4], což umožní využití práce dalšími výzkumníky, jakož i další vylepšení. |
| Seznam odborné literatury |
| [1] Tomáš Kuča: Vizualizační algoritmy pro grafy, bakalářská práce, 2010.
[2] Jakub Kratochvíl: Vizualizace grafů, bakalářská práce, 2008. [3] Michal Zerola: Algoritmy pro kreslení grafů, Diplomová práce, 2005. [4] William A. Stein et al.: Sage Mathematics Software, The Sage Development Team, 2012, http://www.sagemath.org. [5] Graph drawing, http://en.wikipedia.org/wiki/Graph_drawing a citace tam uvedené. Další literatura podle doporučení školitele. |