## Abstract

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(√(g + 1)(k + 1)n) and layered treewidth O((g + 1)k) and that these bounds are tight up to a constant factor. In the special case of g = 0, so-called k-planar graphs, the treewidth bound is O(√(k + 1)n), which is tight and improves upon a known O((k + 1)^{3/4}n^{1/2}) bound. Analogous results are proved for map graphs defined with respect to any surface. Finally, 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.

Original language | English |
---|---|

Pages (from-to) | 805-824 |

Number of pages | 20 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 31 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2017 |

## Keywords

- 1-planar
- Graph minor
- K-planar
- Layered treewidth
- Local crossing number
- Local treewidth
- Map graph
- Pathwidth
- Separator
- Treewidth