The complexity of constrained graph drawing
| Název práce v češtině: | Složitost kreslení grafů s omezeními |
|---|---|
| Název v anglickém jazyce: | The complexity of constrained graph drawing |
| Klíčová slova: | rovinné grafy, částečně vnořené grafy, omezená rovinnost, výpočetní složitost |
| Klíčová slova anglicky: | planar graphs, partially embedded graphs, constrained planarity, computational complexity |
| Akademický rok vypsání: | 2018/2019 |
| 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í: | 26.11.2018 |
| Datum zadání: | 26.11.2018 |
| Datum potvrzení stud. oddělením: | 30.11.2018 |
| Datum a čas obhajoby: | 10.06.2019 09:00 |
| Datum odevzdání elektronické podoby: | 07.05.2019 |
| Datum odevzdání tištěné podoby: | 10.05.2019 |
| Datum proběhlé obhajoby: | 10.06.2019 |
| Oponenti: | RNDr. Jiří Fink, Ph.D. |
| Zásady pro vypracování |
| Řešitel se seznámí s aktuálními výsledky týkajícími se složitosti různých variant problému rovinného kreslení grafů s omezujícími podmínkami, jako jsou třeba problém částečně vnořené rovinnosti a jeho různá zobecnění. Poté se řešitel pokusí navrhnout vhodnou kombinatorickou abstrakci těchto problémů a prozkoumat s využitím této abstrakce hranici mezi jejich polynomiálními a NP-těžkými variantami. Předpokladem pro úspěšné řešení je jednak zvládnutí netriviálních algoritmických technik pro práci s rovinnými nakresleními (SPQR stromy, PQ stromy apod.) a jednak obeznámenost s těžkostními redukcemi využívajícími NP-úplnost některých rovinných verzí problému splnitelnosti. |
| Seznam odborné literatury |
| P. Angelini, G. Di Battista, F. Frati, V. Jelínek, J. Kratochvíl, M. Patrignani, I. Rutter: Testing Planarity of Partially Embedded Graphs, ACM Transactions on Algorithms, 11(4) (2015), Article No. 32, 1-42.
C. Gutwenger, P. Mutzel: A Linear Time Implementation of SPQR-Trees, Graph Drawing, volume 1984 of LNCS (2000), pages 77-90. D. Lichtenstein: Planar Formulae and Their Uses, SIAM Journal on Computing, 11(2) (1982), 329-343. Další časopisecká literatura dle pokynů vedoucího. |