A drawing of a typical graph in the plane usually contains many crossings. A topological graph is a drawing of a
graph in the plane where crossings of edges are allowed, including multiple crossings of the same pair of edges. A
geometric graph is a special case where the edges are drawn as straight-line segments. Finding a drawing of a
graph minimizing the number of crossings is a typical problem in this area. Various extremal problems are also
studied, for example the maximum number of edges of a geometric graph with no k disjoint edges. Basic
knowledge of graph theory and discrete geometry (
Last update: T_KAM (21.04.2016)
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).
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. (19.02.2019)
mostly research papers, a part covered by lecture notes; see https://kam.mff.cuni.cz/~kyncl/tgg/ for details
Last update: doc. Mgr. Jan Kynčl, Ph.D. (19.02.2019)
převážně odborné články, částečně skripta; podrobnosti viz https://kam.mff.cuni.cz/~kyncl/tgg/
Requirements to the exam -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (19.02.2019)
The exam will be oral based on the material that was presented.
Last update: doc. Mgr. Jan Kynčl, Ph.D. (19.02.2019)
Zkouška bude ústní na základě přednesené látky.
Syllabus -
Last update: doc. Mgr. Jan Kynčl, Ph.D. (06.02.2019)
The Hanani--Tutte theorem and an algebraic algorithm for planarity testing
The Jordan curve theorem
Thrackles
Topological and geometric graphs without forbidden substructures
Complete topological graphs
Possibly other topics
Last update: doc. Mgr. Jan Kynčl, Ph.D. (06.02.2019)
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í