Last update: doc. 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.
Last update: doc. Mgr. Jan Kynčl, Ph.D. (25.04.2018)
Průsečíkové číslo grafu je základní grafový parametr, důležitý hlavně pro vizualizaci grafů. Jeho určení je
algoritmicky těžké, dokonce i pro úplné grafy přesná hodnota průsečíkového čísla stále není známá. Kromě
klasického pojmu minimálního počtu křížení v nakreslení v rovině bylo studováno mnoho dalších variant
průsečíkových čísel; v přednášce se zaměříme na několik hlavních z nich. Předpokládají se základní znalosti z
teorie grafů, kombinatorické geometrie (NDMI009) a výpočetní složitosti (pojem NP-úplnosti).
Course completion requirements -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (29.05.2019)
Oral exam.
Last update: doc. Mgr. Jan Kynčl, Ph.D. (29.05.2019)
Ústní zkouška.
Literature -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (25.04.2018)