PLANAR CROSSING NUMBERS OF GRAPHS EMBEDDABLE IN ANOTHER SURFACE
KÁROLY J. BÖRÖZKY, János Pach, Gézá Tóth · International Journal of Foundations of Computer Science · 2006
Let G be a graph of n vertices with maximum degree d that can be drawn without crossing in a closed surface of Euler characteristic χ. It is proved that then G can be drawn in the plane with at most c χ dn crossings, where c χ is a constant depending only on χ. This result, which is tight up to a constant factor, is strengthened and generalized to the case when there is no restriction on the degrees of the vertices.