Sylabus
Hananiova--Tutteova věta a algebraický algoritmus na testování rovinnosti
Jordanova věta o kružnici
Thrackles
Topologické a geometrické grafy bez zakázaných konfigurací
Úplné topologické grafy
Případně další témata
Anotace
Nakreslení typického grafu do roviny se neobejde bez křížení hran. Nakreslením grafů v rovině, v nichž jsou povolena křížení hran, a to i vícenásobná, se říká topologické grafy. Speciálním případem jsou geometrické grafy, jejichž hrany jsou nakresleny jako
úsečky. Typickým problémem při studiu nakreslení grafů je hledání nakreslení s minimálním počtem křížení.
Zkoumají se i různé extremální otázky, jako např. maximální počet hran v geometrickém grafu bez k disjunktních hran.
Předpokládají se základní znalosti z teorie grafů a kombinatorické geometrie (NDMI009).