SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Crossing numbers of graphs - NDMI099
Title in English: Průsečíková čísla grafů
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2018
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: English, Czech
Teaching methods: full-time
Additional information: https://kam.mff.cuni.cz/~kyncl/crossings/
Guarantor: Mgr. Jan Kynčl, Ph.D.
RNDr. Martin Balko, Ph.D.
Class: DS, diskrétní modely a algoritmy
Informatika Mgr. - Diskrétní modely a algoritmy
Kombinatorická geometrie a geom. algorit
Classification: Informatics > Discrete Mathematics
Annotation -
Last update: 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.
Literature -
Last update: 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)

Requirements to the exam -
Last update: Mgr. Jan Kynčl, Ph.D. (19.02.2019)

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

Syllabus -
Last update: 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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html