Úkolem bude zkoumat problémy kreslení grafů v rovině pomocí úseček bez křížení, s vrcholy na zadané množině bodů, zejména varianty s obarvenými vrcholy, a pokusit se o nové výsledky.
The student will investigate problems of drawing graphs with segments in the plane, with vertices in a given point set, in particular variants with colored points, and try to obtain new results.
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
J. Cibulka, J. Kynčl, V. Mészáros, R. Stolař and P. Valtr, Universal sets for straight-line embeddings of bicolored graphs, in: J. Pach (Ed.), Thirty Essays on Geometric Graph Theory, 101-119, Springer, 2013, ISBN 978-1-4614-0109-4.
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.
Preliminary scope of work
Téma může být vhodné i pro práci diplomovou. Více informací na https://kam.mff.cuni.cz/~kyncl/topics.
Preliminary scope of work in English
The topic might be suitable also for a master thesis. See https://kam.mff.cuni.cz/~kyncl/topics_eng for more information.
