  In 1972, Kainen proved a general lower bound on the crossing number of a
graph in a closed surface and conjectured that this bound is tight when the
graph is either a complete graph or a complete bipartite graph, and the surface
is of genus close to the minimum genus of that graph. Prior to the present
work, these conjectures were known to be true only for small cases and when the
conjectures predict a crossing number of 0, i.e., when a triangular or
quadrangular embedding was already known. We show that Kainen's conjectures are
true except for the three graphs $K_9$, $K_{3,5}$, and $K_{5,5}$. We also prove
nonorientable analogues of these conjectures, where the only exceptions to the
general formulas are $K_7$ and $K_8$.
