Subjects

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

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

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

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

Last update: T_KAM (06.05.2001)

Course completion requirements -

Oral exam

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

Literature - Czech

Golumbic: Algorithmic graph theory

Last update: Zakouřil Pavel, RNDr., Ph.D. (05.08.2002)

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 -

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.

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