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

Exercise session 2

  1. Think about various theoretical aspects of the pair and odd crossing numbers, in relation to the presented material. What works also with the alternative definitions (somehow), and where one has to be particularly careful not to make mistakes or false conclusions?
  2. Can you straighforwardly claim that computing the exact pair or odd crossing numbers is NP-complete? (Where is a hidden problem/pitfall?)
  3. Is there some relation between the ordinary crossing number and the crossing number in which edges are drawn as polygonal lines with one bend? 
  4. Think about NP-completeness of the exact rectilinear crossing number. What direction (or part) can you easily prove?
  5. Look up (e.g. on the internet) the construction of [Bounds for rectilinear crossing numbers. Bienstock, Dean, 1993], and explain it shortly.
  6. Come with a short proof that Kochol's construction (see above) gives 2-crossing-critical graphs.
  7. Analyze crossing-criticality of the following construction, try to find a simpler proof. Determine what is the smallest crossing number drop after deleting an edge from this graph (see def. in Day 1). The full paper is referred below, you may read it for an inspiration.
                                    picture
  8. Can you find a k-crossing-critical family (for a fixed k) that contains arbitrarily many vertices of degree 5? And what about degrees 7 or 9? Try to look up some constructions on the internet, or give your own.
Bounds for rectilinear crossing numbers. Bienstock, Dean, 1993
Infinite families of crossing-critical graphs with given average degree (2003). G. Salazar.
Exercise solutions
Předchozí
Následující