Detecting and counting small patterns in planar graphs in subexponential parameterized time
Jesper Nederlof · 2020
We resolve the fine-grained parameterized complexity of detecting and counting small patterns in planar graphs, assuming the Exponential Time Hypothesis. Given an n-vertex planar graph G and a k-vertex pattern graph P, we compute the number of (induced) copies of P in G in time