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

Day 1: Definition, and quantitative aspects

Basics of graph crossing number

  1. What is a drawing of a graph; polygonal arcs.
  2. The standard definition of a crossing number (counting pairwise edge crossings).
  3. Importance. Examples of crossing numbers of particular simple graphs.
  4. Lower bounds from Euler's formula; an advanced quantitative lower bound - the crossing lemma.
  5. Theoretical applications of the crossing lemma.

Finding the crossing number

  1. How to find the exact crossing number, and how to prove it. Frequent problems and pitfalls.
  2. Crossing numbers of several special graph families (complete, complete bipartite, toroidal grids, Petersen graphs).
  3. Other versions of graph crossing number - rectilinear and odd crossing numbers. Examples of difference.