Topological Graphs: Crossing Lemma and Applications
Stefan Felsner · Advanced lectures in mathematics · 2004
Intuitively a handy drawing of a non-planar graph will be a drawing with few crossings. The crossing number of a graph G is the least possible number of pairs of crossing edges in a drawing of G . This measure for the non-planarity of a graph has been studied for more thän thirty years now. The main result is the Crossing Lemma (Theorem 3.3) it provides a lower bound for the crossing number in terms of the numbers of vertices and edges of a graph. In Section 3.3 the constant in the Crossing Lemma is improved. This improvement is an application of bounds for the number of edges of topological graphs with the property that every edge participates at at most one or two crossings. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.