Drawing graphs on surfaces of small genus
| Thesis title in Czech: | Kreslení grafů na plochách malého rodu |
|---|---|
| Thesis title in English: | Drawing graphs on surfaces of small genus |
| Key words: | kreslení grafů, plochy, torus |
| English key words: | graph drawing, surfaces, torus |
| Academic year of topic announcement: | 2012/2013 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 01.11.2012 |
| Date of assignment: | 01.11.2012 |
| Confirmed by Study dept. on: | 23.11.2012 |
| Date and time of defence: | 02.09.2013 00:00 |
| Date of electronic submission: | 01.08.2013 |
| Date of submission of printed version: | 02.08.2013 |
| Date of proceeded defence: | 02.09.2013 |
| Opponents: | doc. Mgr. Robert Šámal, Ph.D. |
| Guidelines |
| 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. |
| References |
| 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. |