SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Geometric Representations of Graphs II - NDMI035
Title in English: Geometrické reprezentace grafů II
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2018
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
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: DS, diskrétní modely a algoritmy
Informatika Mgr. - volitelný
Classification: Informatics > Discrete Mathematics
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).
Literature - Czech
Last update: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)

Golumbic: Algorithmic graph theory

Requirements to the exam - Czech
Last update: prof. RNDr. Jan Kratochvíl, CSc. (12.10.2017)

Zkouška je ústní. Požadavky ke zkoušce odpovídají sylabu v rozsahu předneseném na přednášce.

Syllabus - Czech
Last update: T_KAM (27.03.2004)

NP-úplnost rozpoznávání (průnikové grafy úseček, konvexních množin a křivek).

Velikosti reprezentací (grafy vynucující reprezentace exponenciální velikosti).

Reprezentovatelnost planárních grafů (Koebeho věta o kruzích, bipartitní grafy jako grafy viditelnosti).

Odhady na barevnost jako funkce klikovosti.

Kreslení rovinných grafů na pevnou množinu bodů.

3-dimenzionální kreslení grafů.

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