Crossing numbers of graphs - NDMI099
|
|
||
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.
Last update: Kynčl Jan, doc. Mgr., Ph.D. (25.04.2018)
|
|
||
Oral exam. Last update: Kynčl Jan, doc. Mgr., Ph.D. (29.05.2019)
|
|
||
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) Last update: Kynčl Jan, doc. Mgr., Ph.D. (25.04.2018)
|
|
||
The exam will be oral based on the material that was presented. Last update: Kynčl Jan, doc. Mgr., Ph.D. (19.02.2019)
|
|
||
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 Last update: Kynčl Jan, doc. Mgr., Ph.D. (25.04.2018)
|