## Genus, Treewidth, and Local Crossing Number
Dujmović, Vida and Eppstein, David and Wood, David R.
(2015)
Full text not available from this repository. ## AbstractWe 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<m, every m-edge graph can be embedded on a surface of genus g with O((m/(g+1))log^(2)g) crossings per edge, which is tight to a polylogarithmic factor.
Repository Staff Only: item control page References |