Detecting and counting small patterns in planar graphs in subexponential parameterized time

We present an algorithm that takes as input an n-vertex planar graph G and a k-vertex pattern graph P , and computes the number of (induced) copies of P in G in 2 O(k/ log k) n O(1) time. If P is a matching, independent set, or connected bounded maximum degree graph, the runtime reduces to 2 Õ( √ k) n O(1) . While our algorithm counts all copies of P , it also improves the fastest algorithms that only detect copies of P . Before our work, no 2 O(k/ log k) n O(1) time algorithms for detecting unrestricted patterns P were known, and by a result of Bodlaender et al. [ICALP 2016] a 2 o(k/ log k) n O(1) time algorithm would violate the Exponential Time Hypothesis (ETH). Furthermore, it was only known how to detect copies of a fixed connected bounded maximum degree pattern P in 2 Õ(