Block Course: Methods in Graph Drawing - Crossing Numbers and Crossing Minimization

Day 2: Structural properties, critical graphs

General structural and complexity aspects

  1. Relations between the ordinary and the odd crossing numbers.
  2. An interesting connection - Sylvester's Four point problem.
  3. Computational complexity hardness of determining the exact crossing number.
  4. Fixed-parameter tractability of the crossing number problem.

Crossing-critical graphs

  1. Definition of a critical graph, basic properties of critical graphs.
  2. Overview of crossing-critical constructions; richness of critical graphs.
  3. Deeper structural apsects and properties, and interesting questions.