ABSTRACT
In many respects, crossing minimization is an exceptional problem in the wide range of optimization problems arising in automatic graph drawing. First of all, it is one of the most basic and natural problems among these, and, at the same time, very easy to formulate: given a graph, draw it in the plane with a minimum number of crossings between its edges. In fact, this problem is much older than automatic graph drawing. Crossing number problems were first examined by Tura´n when he worked in a brick factory during the Second World War. This work motivated him to search for crossing minimal drawings of the complete bipartite graph Kn,m, without success. Later, Zarankiewicz gave a rule for creating a drawing of Kn,m with ⌊m2 ⌋⌊m−12 ⌋⌊n2 ⌋⌊n−12 ⌋ crossings, but his proof of optimality was shown to be incorrect. Still today, this is an open question. The same is true for the crossing number of Kn. Besides its theoretical relevance as a topological problem, crossing minimization has many
practical applications. In automatic graph drawing, it is well known that the readability of a two-dimensional graph layout strongly depends on the number of edge crossings. This was verified by empirical studies of Purchase [Pur97]. In fact, the main information given by an abstract graph is whether two vertices are connected by an edge. This information should be easily recognizable. In particular, it should be easily possible to trace the edges in the drawing. This task is complicated by the presence of crossing edges, as they distract the concentration of the human viewer. See Figure 2.1 for a comparison. Another important application for the crossing minimization problem is VLSI (very large
scale integration) design. In this context, the problem was first discussed in depth. The
Figure 2.1 Different drawings of the same abstract graph with different numbers of edge crossings (51, 12, and 4, respectively). Most aesthetic criteria like few edge bends, uniform edge lengths, or a small drawing area favor the first two drawings. However, with respect to the number of edge crossings the last drawing is preferable.
