Drawing graphs on surfaces of small genus

• Název práce v češtině: Kreslení grafů na plochách malého rodu
• Název v anglickém jazyce: Drawing graphs on surfaces of small genus
• Klíčová slova: kreslení grafů, plochy, torus
• Klíčová slova anglicky: graph drawing, surfaces, torus
• Akademický rok vypsání: 2012/2013
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 01.11.2012
• Datum zadání: 01.11.2012
• Datum potvrzení stud. oddělením: 23.11.2012
• Datum a čas obhajoby: 02.09.2013 00:00
• Datum odevzdání elektronické podoby: 01.08.2013
• Datum odevzdání tištěné podoby: 02.08.2013
• Datum proběhlé obhajoby: 02.09.2013
• Oponenti: doc. Mgr. Robert Šámal, Ph.D.

Zásady pro vypracování

Cílem práce je implementovat algoritmy pro kreslení grafů na vybraných plochách malého rodu (torus, případně projektivní rovina či double-torus). Řešení bude zahrnovat vhodné uživatelské rozhraní formou grafového editoru umožňujícího vytváření a editaci grafů a následné úpravy jejich nakreslení na vybraných plochách (v mnohoúhelníkové reprezentaci) a prohlížení 3D modelu.

Seznam odborné literatury

Bojan Mohar and Carsten Thomassen: Graphs on Surfaces, Johns Hopkins University Press, 2001.
William Kocay, Daniel Neilson and Ryan Szypowski: Drawing Graphs on the Torus, Ars Comb. 59 (2001).
Ken-ichi Kawarabayashi, Bojan Mohar and Bruce A. Reed: A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width, proceedings of FOCS 2008, 771-780.
Bojan Mohar: A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface, SIAM J. Discrete Math. 12 (1999), 6-26.
Martin Juvan, Joze Marincek and Bojan Mohar: Embedding a graph in the torus in linear time, proceedings of the 4th International IPCO Conference on Integer Programming and Combinatorial Optimization (1995), 360 - 363.