Relationships between different crossing numbers of graphs

Geza Toth
Renyi Institute of Mathematics

The crossing number of a graph is the minimum number of edge-crossings
over all its drawings. However, one has to be careful with this definition,
because it can be interpreted in several ways. Sometimes it is assumed
that the edges are drawn as straight line segments. We can also assume
that the edges are curves, but any two of them have at most one point in
common. We could also allow several crossings between two edges. We can
count crossing points, or crossing pairs of edges. No matter what definition
we use, the determination of the crossing number of a graph appears to be
an extremely difficult task. I would like to review recent results about the
relationships of the different versions of the crossing number.

Back to Workshop II: Combinatorial Geometry