Planar partition oracles (for bounded degree graphs) in poly(1/\eps) time

Take a planar graph with maximum degree d. These graphs admit a hyperfinite decompositions, where, for a sufficiently small \epsilon > 0, one removes \epsilon dn edges to get connected components of size independent of n. An important tool for sublinear algorithms and property testing for such classes is the partition oracle. A partition oracle is a local procedure that gives "consistent" access to a hyperfinite decomposition, without any preprocessing. Given a query vertex v, the partition oracle outputs the component containing v in time independent of n. All the answers are consistent with a single hyperfinite decomposition. In this talk, I will describe a partition oracle that runs in time poly(d/\epsilon). I will also describe how this machinery strikes a fortune and helps in obtaining a tester for all planar properties which runs in time exp(d/epsilon^2). This is easily obtained by a better error analysis on the seminal result of Newman and Sohler [SICOMP 2013].
Based on Joint works with Sabyasachi Basu, C. Seshadhri and Andrew Stolman.