Sylabus
Varianty průsečíkových čísel (rektilineární, monotónní, párové, liché, nezávislé) a vztahy mezi nimi
Dolní odhady na průsečíková čísla - varianty průsečíkového lemma
Existence podgrafu s vysokým průsečíkovým číslem
Algoritmická složitost určení průsečíkového čísla
Průsečíková čísla úplných grafů
Průsečíková čísla dalších grafů, např. grafů vnořitelných na určitou plochu
Anotace
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).