12
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ 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 $\endgroup$ – Yaroslav Bulatov Dec 12 '10 at 22:55
  • $\begingroup$ I'm sorry... I actually posed the wrong question, forcing me to edit the question above. $\endgroup$ – Radu Curticapean Dec 12 '10 at 23:13
12
$\begingroup$

Yes.

Add a vertex in the middle of the outer face, connected to all the vertices in the outer face; this does not change the genus, and does not decrease the treewidth. Now the graph has a very shallow breadth-first search tree rooted at the new vertex (everything is adjacent to it).

Form a spanning tree of the dual graph whose dual edges are disjoint from the edges of the breadth first search tree. Then there is a set of O(genus) edges that do not belong to either tree. Each of these edges induces a short cycle (a triangle) together with a path in the breadth first search tree, and cutting the surface along these cycles produces a planar surface (see my paper "Dynamic generators of topologically embedded graphs"). That is, if G' is the subgraph of the input graph induced by the vertices that are not endpoints of the O(genus) cut edges, then G' is planar, and its vertices can be covered by O(genus) faces of its planar embedding (the faces that the cut cycles cut the original outer face into).

But in a planar graph in which all vertices belong to k faces, one can remove another O(k) edges (a spanning tree of the faces) to get an outerplanar graph. So the treewidth of G' is O(genus). If one forms a tree-decomposition of G' with this width, and then adds to each bag the vertices that are endpoints of the cut cycle edges, the result is a tree-decomposition of the original input graph with treewidth O(genus).

It seems likely that this must be in the literature already somewhere, but I don't know where and some quick searches haven't succeeded in finding an explicit statement of this precise result. However, a more general statement is in a different paper of mine: in "Diameter and treewidth in minor-closed graph families" I prove among other things that bounded genus graphs of bounded diameter have bounded treewidth. In this case (by adding that extra vertex within the outer face) the diameter can be taken to be at most two.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.