Geometric Representations of Graphs 1 - NDMI037
Title: Geometrické reprezentace grafů 1
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023 to 2023
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Guarantor: prof. RNDr. Jan Kratochvíl, CSc.
doc. RNDr. Vít Jelínek, Ph.D.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics
Opinion survey results   Examination dates   WS schedule   Noticeboard   
Annotation -
Overview of intersection defined classes of graphs, mainly of geometric objects in the plane (interval graphs, circle graphs, circular arc graphs, permutation graphs, cocomparability graphs). Characterization theorems and recognition.
Last update: G_I (26.10.2001)
Course completion requirements -

Oral exam

Last update: Jelínek Vít, doc. RNDr., Ph.D. (10.06.2019)
Requirements to the exam -

The exam is oral. The requirements correspond to the syllabus of the course, as covered by the lectures.

Last update: Jelínek Vít, doc. RNDr., Ph.D. (10.06.2019)
Syllabus -

Intersevtion graph classes: interval, chordal, circular arc, circle, permutation, comparability, segment, convex, and string graphs in the plane.

Characterisation results (interval, chordal, comparability and permutation graphs)

Recognition algorithms (chordal and comparability graphs).

Last update: Jelínek Vít, doc. RNDr., Ph.D. (10.06.2019)