SubjectsSubjects(version: 964)
Course, academic year 2024/2025
   Login via CAS
Crossing numbers of graphs - NDMI099
Title: Průsečíková čísla grafů
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019
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
Additional information: https://kam.mff.cuni.cz/~kyncl/crossings/
Guarantor: doc. Mgr. Jan Kynčl, Ph.D.
doc. RNDr. Martin Balko, Ph.D.
Class: DS, diskrétní modely a algoritmy
Informatika Mgr. - Diskrétní modely a algoritmy
Kombinatorická geometrie a geom. algorit
Classification: Informatics > Discrete Mathematics
Annotation -
The crossing number of a graph is a fundamental graph parameter, important for graph visualisation. Its computation is algorithmically hard, and even for complete graphs the exact value of the crossing number is unknown. Besides the classical notion of the minimum number of crossings in a drawing in the plane, many other variants of crossing numbers have been studied; in this course we focus on several main variants. Basic knowledge of graph theory, discrete geometry (NDMI009) and computational complexity (the notion of NP- completeness) is assumed.
Last update: Kynčl Jan, doc. Mgr., Ph.D. (25.04.2018)
Course completion requirements -

Oral exam.

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

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

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

Variants of crossing numbers (rectilinear, monotone, pair, odd, independent) and relations between them

Lower bounds on crossing numbers - variants of the crossing lemma

Algorithmic complexity of computing the crossing number

Crossing numbers of the complete graphs

Crossing numbers of other graphs, for example graphs embeddable on a fixed surface

Last update: Kynčl Jan, doc. Mgr., Ph.D. (25.04.2018)
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html