Náhodná nakreslení grafů: generování a analýza

• Název práce v češtině: Náhodná nakreslení grafů: generování a analýza
• Název v anglickém jazyce: Random Graph Embeddings: Generation and Analysis
• Klíčová slova: nakreslení grafu|struktura duálu|náhodná nakreslení
• Klíčová slova anglicky: graph embeddings|structure of the dual|random embedding
• Akademický rok vypsání: 2024/2025
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: doc. Mgr. Robert Šámal, Ph.D.
• Řešitel: Bc. Matěj Prokopič - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 06.05.2025
• Datum zadání: 07.05.2025
• Datum potvrzení stud. oddělením: 07.05.2025
• Datum a čas obhajoby: 20.06.2025 09:00
• Datum odevzdání elektronické podoby: 07.05.2025
• Datum odevzdání tištěné podoby: 07.05.2025
• Datum proběhlé obhajoby: 20.06.2025
• Oponenti: RNDr. Radek Hušek, Ph.D.

Zásady pro vypracování

Buněčné nakreslení grafů lze popsat kombinatoricky, viz [1], pomocí lokálních rotací a informací o kříženích na hranách. Pokud tyto informace zvolíme náhodně, získáme model náhodného nakreslení grafu na (náhodnou) plochu, viz např. [2] a reference tam obsažené.

Student naváže na svůj úspěšný ročníkový projekt, kde implementoval procházení stěn pro dané nakreslení a prozkoumá, jak se při náhodném nakreslení chovají různé parametry nakreslení: počty stěn, počty smyček v duálu, atd.

Seznam odborné literatury

[1] Mohar, B.; Thomassen, C. Graphs on Surfaces. Baltimore: Johns Hopkins University Press, 2001.

[2] Campion Loth, J; Halasz, K.; Masařík, T.; Mohar, B.; Šámal, R.
Random embeddings of graphs: the expected number of faces in most graphs is logarithmic.
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1177–1193.