# Do “outer-bounded-genus” graphs have constant treewidth?

Let $k\in\mathbb{N}$ and denote by $G_k$ the set of all graphs that can be embedded on a surface of genus $k$ such that all vertices are situated on the outer face. For instance, $G_0$ is the set of outerplanar graphs. Can the treewidth of graphs in $G_k$ be upper bounded by some function of $k$?

The other direction obviously does not hold, since constant treewidth does not even imply constant genus: Let $H_n$ be the union of $n$ disjoint copies of $K_{3,3}$. The treewidth of $H_n$ is constant, its genus however is $n$.

• Square grid with $n$ nodes has tree width of $O(\sqrt{n})$. There are many problems which are NP-hard on planar graphs but in P for bounded tree width graphs, such as maximum independent set. I have not seen any examples the other way round – Yaroslav Bulatov Dec 12 '10 at 22:55
• I'm sorry... I actually posed the wrong question, forcing me to edit the question above. – Radu Curticapean Dec 12 '10 at 23:13