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: 2012/2013
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: doc. Mgr. Robert Šámal, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 25.06.2013
• Date of assignment: 28.06.2013
• Confirmed by Study dept. on: 12.07.2013

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.