THE CROSSING NUMBER OF A GRAPH ON A COMPACT 2-MANIFOLD

We introduce a general framework to estimate the crossing number of a graph on a compact 2-manifold in terms of the crossing number of the c omplete graph of the same size on the same manifold. The bounds are ti ght within a constant multiplicative factor for many graphs, including hypercubes, some complete bipartite graphs and random graphs. We dete rmine the crossing number of a complete graph, and hence of many other graphs, on a compact 2-manifold up to a polylog genus multiplicative factor. We give estimations for related Turan numbers. (C) 1996 Academ ic Press, Inc.