Drawing geometric graphs on red-blue point sets
| Název práce v češtině: | Kreslení geometrických grafů na červeno-modré množiny bodů |
|---|---|
| Název v anglickém jazyce: | Drawing geometric graphs on red-blue point sets |
| Klíčová slova: | kreslení grafů|geometrický graf|nekřížící se alternující cesta|doubarevná množina bodů|nejdelší společná podposloupnost |
| Klíčová slova anglicky: | graph drawing|geometric graph|non-crossing alternating path|bichromatic point set|longest common subsequence |
| Akademický rok vypsání: | 2020/2021 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | doc. Mgr. Jan Kynčl, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 28.01.2021 |
| Datum zadání: | 28.01.2021 |
| Datum potvrzení stud. oddělením: | 18.02.2021 |
| Datum a čas obhajoby: | 01.07.2021 13:00 |
| Datum odevzdání elektronické podoby: | 21.05.2021 |
| Datum odevzdání tištěné podoby: | 21.05.2021 |
| Datum proběhlé obhajoby: | 01.07.2021 |
| Oponenti: | prof. RNDr. Jan Kratochvíl, CSc. |
| Zásady pro vypracování |
| Úkolem bude zkoumat problémy kreslení grafů v rovině pomocí úseček bez křížení, s vrcholy na zadané červeno-modré množině bodů. Student se zaměří zejména na kreslení alternujících cest, stromů, párování a související kombinatorické otázky.
The student will investigate problems of drawing graphs using segments in the plane, with vertices in a given red-blue point set. The student will focus on drawing of alternating paths, trees, matchings and related combinatorial questions. |
| Seznam odborné literatury |
| J. Kynčl, J. Pach and G. Tóth, Long alternating paths in bicolored point sets, Discrete Mathematics 308 (2008), Issue 19, 4315-4321
A. Kaneko and M. Kano, Discrete Geometry on Red and Blue Points in the Plane - A Survey -, In: Aronov B., Basu S., Pach J., Sharir M. (eds) Discrete and Computational Geometry, Algorithms and Combinatorics, vol 25. Springer, Berlin, Heidelberg, pp 551-570 M. Kano and J. Urrutia, Discrete Geometry on Colored Point Sets in the Plane—A Survey, Graphs and Combinatorics 37 (2021), 1–53. |