The complexity of testing all properties of planar graphs, and the role of isomorphism

Consider property testing on bounded degree graphs and let ε > 0 denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts that all properties of planar graphs (more generally hyperfinite) are testable with query complexity only depending on ε. Recent advances in testing minor-freeness have proven that all additive and monotone properties of planar graphs can be tested in poly(ε -1 ) queries. Some properties falling outside this class, such as Hamiltonicity, also have a similar complexity for planar graphs. Motivated by these results, we ask: can all properties of planar graphs can be tested in poly(ε -1 ) queries? Is there a uniform query complexity upper bound for all planar properties, and what is the "hardest" such property to test?

We discover a surprisingly clean and optimal answer. Any property of bounded degree planar graphs can be tested in exp(O(ε -2 )) queries. Moreover, there is a matching lower bound, up to constant factors in the exponent. The natural property of testing isomorphism to a fixed graph requires exp(Ω(ε -2 )) queries, thereby showing that (up to polynomial dependencies) isomorphism to an explicit fixed graph is the hardest property of planar graphs. The upper bound is a straightforward adapation of the Newman-Sohler analysis that tracks dependencies on ε more carefully. The main technical contribution is the lower bound construction, which is achieved by a special family of planar graphs that are all mutually far from each other.

We can also apply our techniques to get analogous results for bounded treewidth graphs. We prove that all properties of bounded treewidth graphs can be tested in exp(O(ε -1 log ε -1 )) queries. Moreover, testing isomorphism to a fixed forest requires exp(Ω(ε -1 )) queries.