Planar Crossing Numbers of Graphs of Bounded Genus
Pach and Tth proved that any n-vertex graph of genus g and maximum degree d has a planar crossing number at most c (g) dn, for a constant c > 1. We improve on this result by decreasing the bound to O(dgn), and also prove that our result is tight within a constant factor. Our proof is constructive and yields an algorithm with time complexity O(dgn). As a consequence of our main result, we show a relation between the planar crossing number and the surface crossing number.
crossing number genus surface crossing number orientable surface