Interaktivní osnova
Block Course: Methods in Graph Drawing - Crossing Numbers and Crossing Minimization
Day 1: Definition, and quantitative aspects
Basics of graph crossing number
- What is a drawing of a graph; polygonal arcs.
- The standard definition of a crossing number (counting pairwise edge crossings).
- Importance. Examples of crossing numbers of particular simple graphs.
- Lower bounds from Euler's formula; an advanced quantitative lower bound - the crossing lemma.
- Theoretical applications of the crossing lemma.
Finding the crossing number
- How to find the exact crossing number, and how to prove it. Frequent problems and pitfalls.
- Crossing numbers of several special graph families (complete, complete bipartite, toroidal grids, Petersen graphs).
- Other versions of graph crossing number - rectilinear and odd crossing numbers. Examples of difference.