New Intersection Graph Hierachies

• Název práce v češtině: Nové hierarchie průnikových grafů
• Název v anglickém jazyce: New Intersection Graph Hierachies
• Klíčová slova: průnikový graf|string graf|hierarchie|grafový parametr
• Klíčová slova anglicky: intersection graph|string graph|hierarchy|graph parameter
• Akademický rok vypsání: 2021/2022
• Typ práce: diplomová práce
• Jazyk práce: anglič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í: 05.03.2022
• Datum zadání: 08.03.2022
• Datum potvrzení stud. oddělením: 18.03.2022
• Datum a čas obhajoby: 15.09.2022 13:00
• Datum odevzdání elektronické podoby: 20.07.2022
• Datum odevzdání tištěné podoby: 25.07.2022
• Datum proběhlé obhajoby: 15.09.2022
• Oponenti: prof. RNDr. Jan Kratochvíl, CSc.

Zásady pro vypracování

Student se seznámí s existujícími výsledky v oblasti strukturálních, enumerativních a složitostních vlastností průnikových grafů a pokusí se odvodit vlastní nové výsledky v této oblasti. Zvláštní pozornost bude věnována třídám grafů reprezentovatelným pomocí úseček nebo křivek omezené složitosti v rovině, jako jsou úsečkové grafy, intervalové grafy, L-grafy, Stick-grafy apod.

Seznam odborné literatury

Daniel Gonçalves, Lucas Isenmann, and Claire Pennarun: Planar graphs as L-intersection or L-contact graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium
on Discrete Algorithms, SODA 2018, pages 172-184.

Minghui Jiang: Recognizing d-Interval Graphs and d-Track Interval Graphs. Algorithmica 66, 541-563 (2013).

Sergio Cabello and Miha Jejčič: Refining the hierarchies of classes of geometric intersection graphs. Electron. J. Combin., 24(1):Paper 1.33, 19 (2017).