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í
• 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

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: Kynčl Jan, doc. Mgr., Ph.D. (25.04.2018)

angličtina

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.

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

Podmínky zakončení předmětu

čeština

Ústní zkouška.

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

angličtina

Oral exam.

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

Literatura

čeština

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)

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

angličtina

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)

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

Požadavky ke zkoušce

čeština

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

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

angličtina

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

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

Sylabus

čeština

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

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

angličtina

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

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