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í: 2012/2013
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: doc. Mgr. Robert Šámal, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 25.06.2013
• Datum zadání: 28.06.2013
• Datum potvrzení stud. oddělením: 12.07.2013

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.