Geometrické reprezentace grafů

• Thesis title in Czech: Geometrické reprezentace grafů
• Thesis title in English: Geometric representations of graphs
• Academic year of topic announcement: 2009/2010
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: prof. RNDr. Jan Kratochvíl, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 09.11.2009
• Date of assignment: 09.11.2009
• Date and time of defence: 17.09.2010 00:00
• Date of electronic submission: 17.09.2010
• Date of proceeded defence: 17.09.2010
• Opponents: RNDr. Martin Pergel, Ph.D.

Guidelines

The student will study geometric representations of graphs such as intersection graphs, inclusion representations, geometrically motivated discrete structures and others. Main attention will be paid to recongition of such structures and algorithms for the basic optimization problems on them.

References

McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, Philadelphia: Society for Industrial and Applied Mathematics (SIAM Monographs on Discrete Mathematics and Applications, No. 2), MR1672910, ISBN 0-89871-430-3

Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-444-51530-5, Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.

aktuální časopisecká literatura podle zadání vedoucího

Preliminary scope of work

Geometrické reprezentace grafů, jejich rozpoznávání a algoritmy na nich.

Preliminary scope of work in English

Geometric representations of graphs, their recognition and algorithms on them.