Crossing Numbers of Graphs

János Pach
Rényi Institute,
Budapest and Courant Institute,
New York, USA

Abstract
The crossing number of a graph G is the minimal number of edge crossings in a drawing of G in the plane. A common interior point (crossing) of k edges contributes to this number. After giving a short review of the subject, we discuss several new results concerning this parameter. For instance, we prove that if a graph of n vertices can be drawn without crossing on a torus, then its crossing number (in the plane) is at most O(Dn), where D denotes the maximum degree of the vertices. What happens if we slightly change the definition, as follows? We define the degenerate crossing number of G just like above, with the difference that k-wise crossings are now counted only once. Are we up to a surprise? For instance, does the famous crossing lemma of Leighton and Ajtai et al. remain true for this new parameter? Is it true that the degenerate crossing number of a graph with n vertices and e edges is always at least ? The answer is (perhaps) yes and no.