NDMI035 Geometrické reprezentace grafů II - LS 2020

Dosud probraná témata:

24. 2. a 2. 3.: Rozpoznávání STRING v NP

Literatura:
M. Schaefer, E. Sedgwick, D. Štefankovič: Recognizing string graphs in NP. Journal of Computer and System Sciences 67, 365-380, 2003.

9. 3.: Reprezentace 3-obarvitelných rovinných grafů jako průnikových grafů úseček tří směrů

Literatura:
D. Gonçalves: 3-colorable planar graphs have an intersection segment representation using 3 slopes. Konferenční verze (ve které chybí některé důkazy): Sau I., Thilikos D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2019. Lecture Notes in Computer Science, vol 11789.

16. 3.: Samostudium výše uvedeného Gonçalvesova výsledku.

23. 3.: Dotykové reprezentace rovinných grafů a jejich kreslení na malou mřížku.

30. 3.: Složitost CLIQUE v průnikových grafech.

6. 4.: SEG a CONV grafy

20. 4.: Dokončování částečných reprezentací

27. 4.: Dokončování částečných reprezentací - FUN grafy

4. 5.: Dokončování částečných reprezentací - FUN grafy (pokračování)

15. 5.: Koebeho věta

22. 5.: Částečně vnořená rovinnost

P. Angelini et al.: Testing planarity of partially embedded graphs, ACM Transactions on Algorithms, 11(4) (2015), Article No. 32, 1-42