SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Geometric Representations of Graphs 2 - NDMI035
Title: Geometrické reprezentace grafů 2
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: English
Teaching methods: full-time
Teaching methods: full-time
Guarantor: prof. RNDr. Jan Kratochvíl, CSc.
doc. RNDr. Vít Jelínek, Ph.D.
Class: DS, diskrétní modely a algoritmy
Informatika Mgr. - volitelný
Classification: Informatics > Discrete Mathematics
Is incompatible with: NDMI019
Is interchangeable with: NDMI019
Annotation -
Last update: 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).
Course completion requirements -
Last update: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)

Oral exam

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.

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.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html