Ú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.
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
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.
Předběžná náplň práce
Téma může být vhodné i pro práci bakalářskou. Více informací na https://kam.mff.cuni.cz/~kyncl/topics.
Předběžná náplň práce v anglickém jazyce
The topic might be suitable also for a bachelor thesis. See https://kam.mff.cuni.cz/~kyncl/topics_eng for more information.
