Advanced course in Computer Science
Intersection and contact representations of graphs, including interval graphs,
chordal graphs, circle graphs, circular-arc graphs, segment-intersection graphs,
string graphs. Characterization theorems, NP-hardness results for recognition.
Sizes of representations. Optimization algorithms for classes of intersection
graphs. Representations of planar graphs (kissing lemma, visibility
representations, drawing on small size grid).
Last update: T_KAM (27.03.2004)
Průnikové grafy především geometricky definované - algoritmy a
charakterizační věty. Volně navazuje na Geometrické reprezentace grafů I (DMI037). Vhodné pro 5.ročník a PGS.
Course completion requirements -
Last update: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
Oral exam
Last update: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
Ústní zkouška
Literature - Czech
Last update: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)
Golumbic: Algorithmic graph theory
Requirements to the exam -
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: prof. RNDr. Jan Kratochvíl, CSc. (12.10.2017)
Zkouška je ústní. Požadavky ke zkoušce odpovídají sylabu v rozsahu předneseném na přednášce.
Syllabus -
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.
Last update: T_KAM (27.03.2004)
NP-úplnost rozpoznávání (průnikové grafy úseček, konvexních množin a křivek).
Velikosti reprezentací (grafy vynucující reprezentace exponenciální velikosti).
Reprezentovatelnost planárních grafů (Koebeho věta o kruzích, bipartitní grafy jako grafy viditelnosti).