# Problem 38: Query Complexity of Local Partitioning Oracles

The best known oracle for bounded-degree planar graphs makes at most $d^{\operatorname{poly}(1/\epsilon)}$ queries to the underlying graph to answer each query about the resulting partition, where $d$ is the bound on the maximum vertex degree in the graph. See [Onak-10] for a description of the method.
Question: Can one design an oracle that makes only $\operatorname{poly}(d/\epsilon)$ queries? If so, then among other things, this would lead to a tester for planarity in the bounded-degree model that makes only $\operatorname{poly}(1/\epsilon)$ queries, resolving an open question of Benjamini et al. [BenjaminiSS-08].
Levi and Ron [LeviR-13] showed a partitioning oracle for bounded-degree minor-free graphs that makes only $(d/\epsilon)^{O(\log(1/\epsilon))}$ queries to the input graph for each query about the partition.