Algoritmus pro dokreslování rovinných nakreslení

• Thesis title in Czech: Algoritmus pro dokreslování rovinných nakreslení
• Thesis title in English: An algorithm for extending partial planar drawings
• Key words: rovinnost, algoritmus, částečně vnořené grafy
• English key words: planarity, algorithm, partially embedded graphs
• Academic year of topic announcement: 2016/2017
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: doc. RNDr. Vít Jelínek, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 06.02.2017
• Date of assignment: 06.02.2017
• Confirmed by Study dept. on: 18.05.2017
• Date and time of defence: 20.06.2017 00:00
• Date of electronic submission: 18.05.2017
• Date of submission of printed version: 18.05.2017
• Date of proceeded defence: 20.06.2017
• Opponents: doc. Mgr. Robert Šámal, Ph.D.

Guidelines

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.

References

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.