Poslední úprava: 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).
Poslední úprava: 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.
Podmínky zakončení předmětu -
Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (29.05.2019)
Ústní zkouška.
Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (29.05.2019)
Oral exam.
Literatura -
Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (25.04.2018)