A Near-Optimal Planarization Algorithm

The problem of testing whether a graph is planar has been studied for over half a century, and is known to be solvable in ( n ) time using a myriad of different approaches and techniques. Robertson and Seymour established the existence of a cubic algorithm for the more general problem of deciding whether an n -vertex graph can be made planar by at most k vertex deletions, for every fixed k. Of the known algorithms for k -V ertex P lanarization, the algorithm of Marx and Schlotter (WG 2007, Algorithmica 2012) running in time achieves the best running time dependence on k. The algorithm of Kawarabayashi (FOCS 2009), running in time f ( k ) n for some f ( k ) ∊ that is not stated explicitly, achieves the best dependence on n. In this paper we present an algorithm for k -Vertex Planarization with running time 2 ( k log k ) · n, significantly improving the running time dependence on k without compromising the linear dependence on n. Our main technical contribution is a novel scheme to reduce the treewidth of the input graph to ( k ) in time 2 O ( k log k ) · n. It combines new insights into the structure of graphs that become planar after contracting a matching, with a Baker-type subroutine that reduces the number of disjoint paths through planar parts of the graph that are not affected by the sought solution. To solve the reduced instances we formulate a dynamic programming algorithm for W eighted V ertex P lanarization on graphs of treewidth w with running time 2 ( w log w ) · n, thereby improving over previous double-exponential algorithms. While Kawarabayashi's planarization algorithm relies heavily on deep results from the graph minors project, our techniques are elementary and practically self-contained. We expect them to be applicable to related edge-deletion and contraction variants of planarization problems.

Authors

• Bart M. P. Jansen
• Daniel Lokshtanov
• Saket Saurabh 0001

Keywords

No keywords are indexed for this paper.