Subexponentially solvable hard graph problems In light of the recent result of Arora, Barak, and Steurer, Subexponential Algorithms for Unique Games and Related Problems, I'm interested in graph problems that have subexponential time algorithms but believed not to be polynomially solvable. A famous example is graph isomorphism which has subexponential algorithm of $2^{O(n^{1/2} \log n)}$ run-time. Another example is log-Clique problem which is solvable in quasi-polynomial time ($n^{O(\log n)}$).


  I'm looking for interesting examples and preferably a reference to surveys of subexponential hard graph problems (not necessarily $NP$-complete). Also, Are there any $NP$-complete graph problems with subexponential time algorithms?


Impagliazzo, Paturi and Zane showed that the Exponential Time Hypothesis implies that Clique, k-Colorability, and Vertex Cover need $2^{\Omega(n)}$ time.
Since every planar graph on $n$ vertices has treewidth $O(\sqrt{n})$, all problems which are solvable in $O^*(2^{O(k)})$ time for graphs of treewidth at most~$k$ (there are a LOT of such problems) have subexponential-time algorithms on planar graphs by computing a constant-factor approximation to the treewidth in polynomial-time (for example by computing the branchwidth with the ratcatcher algorithm) and then running the treewidth algorithm, resulting in runtimes of the form $O^*(2^{O(\sqrt{n})})$ for graphs on $n$ vertices. Examples are Planar Independent Set and Planar Dominating Set, which are NP-complete of course.