Structural and complexity aspects of intersection representations

• Název práce v češtině: Strukturální a složitostní aspekty průnikových reprezentací
• Název v anglickém jazyce: Structural and complexity aspects of intersection representations
• Klíčová slova: struktura|složitost|průniková reprezentace
• Klíčová slova anglicky: structure|complexity|intersection representation
• Akademický rok vypsání: 2023/2024
• Typ práce: bakalářská 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í: 10.11.2023
• Datum zadání: 10.11.2023
• Datum potvrzení stud. oddělením: 10.11.2023
• Datum a čas obhajoby: 06.09.2024 09:00
• Datum odevzdání elektronické podoby: 18.07.2024
• Datum odevzdání tištěné podoby: 18.07.2024
• Datum proběhlé obhajoby: 06.09.2024
• Oponenti: RNDr. Martin Pergel, Ph.D.

Zásady pro vypracování

Student se seznámí s aktuálními vědeckými poznatky týkajícími se složitosti rozpoznávání a strukturálních vlastností grafů definovaných pomocí specifických průnikových reprezentací. Zvláštní pozornost bude věnována reprezentacím odvozeným od L-grafů a outer-string grafů. Student se následně pokusí vyřešit otevřené problémy v této oblasti.

Seznam odborné literatury

Brandstädt, Le, Spinrad: "Graph Classes: A Survey", SIAM, 1999.

Dibyayan Chakraborty, Kshitij Gajjar, Irena Rusu: Recognizing Geometric Intersection Graphs Stabbed by a Line, arXiv:2209.01851v2, 2023.

V. Jelínek, M. Töpfer: On grounded L-graphs and their relatives, Electronic Journal of Combinatorics, 26(3) (2019), article P3.17.