Divide-and-conquer strategy based on variations of the Lipton-Tarjan planar separator theorem has been one of the most common approaches for solving planar graph problems for more than 20 years. We present a new framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our approach is based on geometric properties of planar branch decompositions obtained by Seymour & Thomas, combined with new techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. Compared to divide-and-conquer algorithms, the main advantages of our method are a) it is a generic method which allows to attack broad classes of problems; b) the obtained algorithms provide a better worst case analysis. To exemplify our approach we show how to obtain an O(2~(6.903 n~(1/2))n~(3/2) + n~3) time algorithm solving weighted HAMILTONIAN CYCLE. We observe how our technique can be used to solve PLANAR GRAPH TSP in time O(2~(10.8224 n~(1/2))n~(3/2) + n~3). Our approach can be used to design parameterized algorithms as well. For example we introduce the first 2~(O (k~(1/2)))K~(O(1)) • n~(O(1)) time algorithm for parameterized PLANAR k—CYCLE by showing that for a given k we can decide if a planar graph on n vertices has a cycle of length ≥ k in time O(2~(13.6 k~(1/2))k~(1/2) n + n~3).
展开▼
