SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Topological and geometric graphs - NDMI095
Title: Topologické a geometrické grafy
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
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, Czech
Teaching methods: full-time
Teaching methods: full-time
Additional information: https://kam.mff.cuni.cz/~kvgweb/tgg
Guarantor: doc. Mgr. Jan Kynčl, Ph.D.
doc. RNDr. Pavel Valtr, Dr.
Class: DS, diskrétní modely a algoritmy
Informatika Mgr. - Diskrétní modely a algoritmy
Kombinatorická geometrie a geom. algorit
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: T_KAM (21.04.2016)
A drawing of a typical graph in the plane usually contains many crossings. A topological graph is a drawing of a graph in the plane where crossings of edges are allowed, including multiple crossings of the same pair of edges. A geometric graph is a special case where the edges are drawn as straight-line segments. Finding a drawing of a graph minimizing the number of crossings is a typical problem in this area. Various extremal problems are also studied, for example the maximum number of edges of a geometric graph with no k disjoint edges. Basic knowledge of graph theory and discrete geometry (
Course completion requirements -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (29.05.2019)

Oral exam.

Literature -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (19.02.2019)

mostly research papers, a part covered by lecture notes; see https://kam.mff.cuni.cz/~kyncl/tgg/ for details

Requirements to the exam -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (19.02.2019)

The exam will be oral based on the material that was presented.

Syllabus -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (06.02.2019)

The Hanani--Tutte theorem and an algebraic algorithm for planarity testing

The Jordan curve theorem

Thrackles

Topological and geometric graphs without forbidden substructures

Complete topological graphs

Possibly other topics

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