Interaktivní osnova
Block Course: Methods in Graph Drawing - Crossing Numbers and Crossing Minimization
Day 2: Structural properties, critical graphs
General structural and complexity aspects
- Relations between the ordinary and the odd crossing numbers.
- An interesting connection - Sylvester's Four point problem.
- Computational complexity hardness of determining the exact crossing number.
- Fixed-parameter tractability of the crossing number problem.
Crossing-critical graphs
- Definition of a critical graph, basic properties of critical graphs.
- Overview of crossing-critical constructions; richness of critical graphs.
- Deeper structural apsects and properties, and interesting questions.