Algoritmus pro dokreslování rovinných nakreslení

• Název práce v češtině: Algoritmus pro dokreslování rovinných nakreslení
• Název v anglickém jazyce: An algorithm for extending partial planar drawings
• Klíčová slova: rovinnost, algoritmus, částečně vnořené grafy
• Klíčová slova anglicky: planarity, algorithm, partially embedded graphs
• Akademický rok vypsání: 2016/2017
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: doc. RNDr. Vít Jelínek, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 06.02.2017
• Datum zadání: 06.02.2017
• Datum potvrzení stud. oddělením: 18.05.2017
• Datum a čas obhajoby: 20.06.2017 00:00
• Datum odevzdání elektronické podoby: 18.05.2017
• Datum odevzdání tištěné podoby: 18.05.2017
• Datum proběhlé obhajoby: 20.06.2017
• Oponenti: doc. Mgr. Robert Šámal, Ph.D.

Zásady pro vypracování

Student se seznámí s dosavadními výsledky týkajícími se problému částečně vnořené rovinnosti. Následně se student pokusí nalézt a implementovat algoritmus řešící tento problém, který bude pokud možno jednodušší než dosud známé lineární algoritmy (které zatím nebyly implementovány) a zároveň bude mít pokud možno lineární časovou složitost. Součástí práce bude podrobný popis i důkaz správnosti nalezeného algoritmu.

Seznam odborné literatury

P. Angelini, G. Di Battista, F. Frati, V. Jelínek, J. Kratochvíl, M. Patrignani, I. Rutter: Testing Planarity of Partially Embedded Graphs, ACM Transactions on Algorithms, 11(4) (2015), Article No. 32, 1-42.

V. Jelínek, J. Kratochvíl, I. Rutter: A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs, Computational Geometry - Theory and Applications, 46(4) (2013), 466-492.