Extending the branch-decomposition algorithm for planar graphs to broader class of graphs

点击翻译按钮获取中文摘要

We have developed a (1+2g/3)-approximation algorithm for the branch-decomposition of graph G embedded in an orientable surface of genus g. This result is based on an inequality bw(G)≧(3/2)fw(G), where bw(G) is the branchwidth of G and fw (G) is the face-width of G. We also have shown the inequality bw(G)≦3gm (G) for planar graphs, where gm(G) is the size of the largest grid minor of G and, based on this inequality, have developed a fast constant-factor approximation algorithm for the branch-decomposition of planar graphs.