Genus, Treewidth, and Local Crossing Number

We consider relations between the size, treewidth, and local crossing number (maximum crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth O( gkn) and layered treewidth O(gk), and that these bounds are tight up to a constant factor. As a special case, the k-planar graphs with n vertices have treewidth O( kn) and layered treewidth O(k), which are tight bounds that improve a previously known O(k3/4n1/2) treewidth bound. Additionally, we show that for g < m, every m-edge graph can be embedded on a surface of genus g with O((m/g) log2 g) crossings per edge, which is tight to within a polylogarithmic factor.