Průsečíková čísla grafů - NDMI099

• Anglický název: Crossing numbers of graphs
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2019
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: https://kam.mff.cuni.cz/~kyncl/crossings/
• Garant: doc. Mgr. Jan Kynčl, Ph.D.; doc. RNDr. Martin Balko, Ph.D.
• Třída: DS, diskrétní modely a algoritmy; Informatika Mgr. - Diskrétní modely a algoritmy; Kombinatorická geometrie a geom. algorit
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

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).

angličtina

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

čeština

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (29.05.2019)

Ústní zkouška.

angličtina

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (29.05.2019)

Oral exam.

Literatura

čeština

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (25.04.2018)

Marcus Schaefer, The Graph Crossing Number and its Variants: A Survey, The Electronic Journal of Combinatorics, Dynamic Survey DS21 (2017), http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS21

Marcus Schaefer, Crossing numbers of graphs, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2018, ISBN: 978-1-4987-5049-3

Odborné články (bude upřesněno)

angličtina

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (25.04.2018)

Marcus Schaefer, The Graph Crossing Number and its Variants: A Survey, The Electronic Journal of Combinatorics, Dynamic Survey DS21 (2017), http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS21

Marcus Schaefer, Crossing numbers of graphs, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2018, ISBN: 978-1-4987-5049-3

research papers (to be specified)

Požadavky ke zkoušce

čeština

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (19.02.2019)

Zkouška bude ústní na základě přednesené látky.

angličtina

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (19.02.2019)

The exam will be oral based on the material that was presented.

Sylabus

čeština

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (25.04.2018)

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

angličtina

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (25.04.2018)

Variants of crossing numbers (rectilinear, monotone, pair, odd, independent) and relations between them

Lower bounds on crossing numbers - variants of the crossing lemma

Algorithmic complexity of computing the crossing number

Crossing numbers of the complete graphs

Crossing numbers of other graphs, for example graphs embeddable on a fixed surface