Interaktivní osnova
Block Course: Methods in Graph Drawing - Crossing Numbers and Crossing Minimization
Exercise session 1
- Determine the crossing numbers of the following graphs; i.e., find (by hand) a drawing minimizing crossing and also prove that no better drawing may exist..
- Find an infinite sequence of 3-regular simple graphs such that their crossing number grows to infinity. Prove your answer. Can you construct such a sequence being also 3-connected?
- A planarizing edge e in a graph G is such an edge that removing it leaves a planar graph G-e. Prove that (by a suitable construction) a graph with a planarizing edge may have arbitrarily high crossing number. Is it true that in a crossing-optimal drawing of such a graph G all crossings belong to the planarizing edge e?
- Having a graph G of nonzero crossing number x, consider the question of what is the crossing number of the graph G-e obtained by removing an arbitrary one edge e. We call this difference cr(G)-cr(G-e) the crossing number drop after removing e. This drop is usually 0 or 1, but in some cases, for some edges, it may be very high (cf. the previous exercise, planarizing edges). Within this question you have to find examples of graphs, in which the crossing number drop is high for every edge of the considered graph. Do the best you can, and do not forget a proof. (Hint: consider highly symmetric graphs. How are they useful?)
- Look up, e.g. on the internet, the currently best known coefficient in the crossing lemma (the lower bound).
- Find an example of a graph G such that in every optimal drawing of G every edge is crossed. (It is useful to use "heavy edges"...)
- Can you find an example of a point configuration in the plane with a superlinear number of unit distances?
Exercise solutions