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.
Poslední úprava: T_KAM (06.05.2001)
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).
Podmínky zakončení předmětu -
Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
Ústní zkouška
Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
Oral exam
Literatura
Poslední úprava: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)
Golumbic: Algorithmic graph theory
Požadavky ke zkoušce -
Poslední úprava: 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.
Poslední úprava: 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.
Sylabus -
Poslední úprava: 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).
Odhady na barevnost jako funkce klikovosti.
Kreslení rovinných grafů na pevnou množinu bodů.
3-dimenzionální kreslení grafů.
Poslední úprava: 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.