|
|
|
||
Last update: T_KAM (06.05.2001)
|
|
||
Last update: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
Oral exam |
|
||
Last update: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)
Golumbic: Algorithmic graph theory |
|
||
Last update: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
The exam is oral. The requirements correspond to the syllabus of the course, as covered by the lectures. |
|
||
Last update: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
NP-hardness of recognition (intersection graphs of segments, convex sets and strings).
Sizes of representation (graphs requiring representations of exponential size).
Representability of planar graphs (Koebe's theorem on touching circles, bipartite graphs as visibility graphs).
Bounds on chromatic number as a function of the clique number.
Drawing planar graphs on a fixed point set.
3-dimensional graph representation.
|