SubjectsSubjects(version: 861)
Course, academic year 2019/2020
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 [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
Language: English, Czech
Teaching methods: full-time
Additional information:
Guarantor: Mgr. Jan Kynčl, Ph.D.
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 -
Last update: Mgr. Jan Kynčl, Ph.D. (25.04.2018)
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.
Course completion requirements -
Last update: Mgr. Jan Kynčl, Ph.D. (29.05.2019)

Oral exam.

Literature -
Last update: Mgr. Jan Kynčl, Ph.D. (25.04.2018)
Marcus Schaefer, The Graph Crossing Number and its Variants: A Survey, The Electronic Journal of Combinatorics, Dynamic Survey DS21 (2017),

Marcus Schaefer, Crossing numbers of graphs, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2018, ISBN: 978-1-4987-5049-3

research papers (to be specified)

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

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

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

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

Charles University | Information system of Charles University |