A simple and fast approach for solving problems on planar graphs

It is well known that the celebrated Lipton-Tarjan planar separation theorem, in a combination with a divide-and-conquer strategy leads to many complexity results for planar graph problems. For example, by using this approach, many planar graph problems can be solved in time 2°(√n), where n is the number of vertices. However, the constants hidden in big-Oh, usually are too large to claim the algorithms to be practical even on graphs of moderate size. Here we introduce a new algorithm design paradigm for solving problems on planar graphs. The paradigm is so simple that it can be explained in any textbook on graph algorithms: Compute tree or branch decomposition of a planar graph and do dynamic programming. Surprisingly such a simple approach provides faster algorithms for many problems. For example, INDEPENDENT SET on planar graphs can be solved in time O(2^3.182√nn + n ⁴) and DOMINATING SET in time O(2^5.043√nn + n ⁴). In addition, significantly broader class of problems can be attacked by this method. Thus with our approach, LONGEST CYCLE on planar graphs is solved in time O(2^{2.29√n(ln n+0.94)}n^5/4 + n ⁴) and BISECTION is solved in time O(2 ^3.182√nn+n⁴). The proof of these results is based on complicated combinatorial arguments that make strong use of results derived by the Graph Minors Theory. In particular we prove that branch-width of a planar graph is at most 2.122√n. In addition we observe how a similar approach can be used for solving different fixed parameter problems on planar graphs. We prove that our method provides the best so far exponential speed-up for fundamental problems on planar graphs like VERTEX COVER, (WEIGHTED) DOMINATING SET, and many others.