Syllabus
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
Annotation
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.