Planar Graphs · Number of Crossings

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

Problem. Test your intuition! What is \(\operatorname{cr}(K_{n})\), i.e., the minimum number of crossings in a drawing of the complete graph on \(n\) vertices?

5 points

  1. \(\Theta(n)\)

  2. \(\Theta(n\log n)\)

  3. \(\Theta(n^{2})\)

  4. \(\Theta(n^{3})\)

  5. \(\Theta(n^{4})\)

  6. \(\Theta(n^{5})\)

  7. \(\Theta(n^{6})\)