Drawing geometric graphs on red-blue point sets
| Thesis title in Czech: | Kreslení geometrických grafů na červeno-modré množiny bodů |
|---|---|
| Thesis title in English: | Drawing geometric graphs on red-blue point sets |
| Key words: | kreslení grafů|geometrický graf|nekřížící se alternující cesta|doubarevná množina bodů|nejdelší společná podposloupnost |
| English key words: | graph drawing|geometric graph|non-crossing alternating path|bichromatic point set|longest common subsequence |
| Academic year of topic announcement: | 2020/2021 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. Mgr. Jan Kynčl, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 28.01.2021 |
| Date of assignment: | 28.01.2021 |
| Confirmed by Study dept. on: | 18.02.2021 |
| Date and time of defence: | 01.07.2021 13:00 |
| Date of electronic submission: | 21.05.2021 |
| Date of submission of printed version: | 21.05.2021 |
| Date of proceeded defence: | 01.07.2021 |
| Opponents: | prof. RNDr. Jan Kratochvíl, CSc. |
| Guidelines |
| Ú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. |
| References |
| 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. |