Kreslení grafů na plochy mod 2
| Název práce v češtině: | Kreslení grafů na plochy mod 2 |
|---|---|
| Název v anglickém jazyce: | Drawing graphs on surfaces mod 2 |
| Klíčová slova: | kreslení grafů, rod grafu, Z2-rod grafu, Hanani–Tutteova věta |
| Klíčová slova anglicky: | drawing of graphs, genus of a graph, Z2-genus of a graph, Hanani–Tutte theorem |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | diplomová práce |
| Jazyk práce: | |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | doc. Mgr. Jan Kynčl, Ph.D. |
| Řešitel: |
| Zásady pro vypracování |
| Z2-rod grafu G je nejmenší rod ("počet děr") orientovatelné plochy, na kterou jde G nakreslit tak, že hrany bez společného vrcholu mají sudý počet křížení. Úkolem bude pokusit se spočítat nebo odhadnout Z2-rod nebo příbuzné parametry konkrétních grafů nebo jejich tříd.
The Z2-genus of a graph G is the smallest genus ("number of holes") of the orientable surface where G can be drawn so that edges with no common vertex cross an even number of times. The goal will be to compute or estimate the Z2-genus or related parameters of particular graphs or their classes. |
| Seznam odborné literatury |
| R. Fulek, J. Kynčl and D. Pálvölgyi, Unified Hanani–Tutte theorem, The Electronic Journal of Combinatorics 24 (2017), Issue 3, P3.18, 8 pp.
R. Fulek and J. Kynčl, Counterexample to an extension of the Hanani–Tutte theorem on the surface of genus 4 (with R. Fulek), Combinatorica 39 (2019), Issue 6, 1267-1279. R. Fulek and J. Kynčl, The Z2-genus of Kuratowski minors, arXiv:1803.05085. Extended abstract in: Proceedings of the 34th International Symposium on Computational Geometry (SoCG 2018), Leibniz International Proceedings in Informatics (LIPIcs) 99, 40:1--40:14, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. R. Fulek and J. Kynčl, Z2-genus of graphs and minimum rank of partial symmetric matrices, arXiv:1903.08637. Extended abstract in: Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019), Leibniz International Proceedings in Informatics (LIPIcs) 129, 39:1--39:16, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. M. Schaefer and D. Štefankovic, Block additivity of Z2-embeddings, Graph drawing, Lecture Notes in Computer Science 8242, 185–195, Springer, 2013. |
| Předběžná náplň práce |
| Téma může být vhodné i pro práci bakalářskou. Více informací na https://kam.mff.cuni.cz/~kyncl/topics. |
| Předběžná náplň práce v anglickém jazyce |
| The topic might be suitable also for a bachelor thesis. See https://kam.mff.cuni.cz/~kyncl/topics_eng for more information. |