SubjectsSubjects(version: 916)
Course, academic year 2022/2023
   Login via CAS
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 2022
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: not taught
Language: Czech
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
Annotation -
Last update: G_I (26.10.2001)
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.
Course completion requirements -
Last update: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)

Oral exam

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.

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

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).

Charles University | Information system of Charles University |