Genus, Treewidth, and Local Crossing Number
Vida Dujmović, David Eppstein, David R. Wood · Lecture notes in computer science · 2015
We consider relations between the size, treewidth, and local crossing number (maximum number of 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(\sqrt{(g+1)(k+1)n})$$ and layered treewidth $$O((g+1)k)$$ , 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(\sqrt{(k+1)n})$$ and layered treewidth $$O(k+1)$$ , which are tight bounds that improve a previously known $$O((k+1)^{3/4}n^{1/2})$$ treewidth bound. Additionally, we show that for $$g