Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

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 2024
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:	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

Opinion survey results Examination dates 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)