Praktické kreslení grafů pro teorii grafů
Thesis title in Czech: | Praktické kreslení grafů pro teorii grafů |
---|---|
Thesis title in English: | Practical graph drawing for graph theory |
Key words: | kreslení grafů, struktura |
English key words: | graph drawing, structure |
Academic year of topic announcement: | 2019/2020 |
Thesis type: | Bachelor's thesis |
Thesis language: | |
Department: | Computer Science Institute of Charles University (32-IUUK) |
Supervisor: | doc. Mgr. Robert Šámal, Ph.D. |
Author: |
Guidelines |
Ú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í. |
References |
[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. |