While most NP-hard graph problems remain NP-hard when restricted to planar graphs, they become somewhat simpler: they often admit algorithms with running time exponential in the square root of the size of the graph (or some other meaningful parameter). This behavior has been dubbed "the square root phenomenon". For many problems, such an algorithm follows from the theory of bidimensionality relying on a linear dependency on the size of the largest grid minor and treewidth of a planar graph. In recent years we have seen a number of other algorithmic techniques, significantly extending the boundary of the applicability of the "square root phenomenon". In my talk I will survey this area and highlight main algorithmic approaches.

Nov 26, 2018 | 02:15 PM

Humboldt-Universität zu Berlin

Institut für Informatik

Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading])

Johann von Neumann-Haus

Rudower Chaussee 25

12489 Berlin