Structural and complexity aspects of intersection representations
| Thesis title in Czech: | Strukturální a složitostní aspekty průnikových reprezentací |
|---|---|
| Thesis title in English: | Structural and complexity aspects of intersection representations |
| Key words: | struktura|složitost|průniková reprezentace |
| English key words: | structure|complexity|intersection representation |
| Academic year of topic announcement: | 2023/2024 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | anglič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: | 10.11.2023 |
| Date of assignment: | 10.11.2023 |
| Confirmed by Study dept. on: | 10.11.2023 |
| Date and time of defence: | 06.09.2024 09:00 |
| Date of electronic submission: | 18.07.2024 |
| Date of submission of printed version: | 18.07.2024 |
| Date of proceeded defence: | 06.09.2024 |
| Opponents: | RNDr. Martin Pergel, Ph.D. |
| Guidelines |
| 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. |
| References |
| 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. |