Partition Oracles for Planar Graphs and Minor-Free Graphs in General

A partition oracle is a procedure that, given access to the incidence lists representation of a bounded-degree graph $G= (V,E)$ and a parameter $\epsilon$, when queried on a vertex $v\in V$, returns the part (subset of vertices) that $v$ belongs to in a partition of all graph vertices. The partition should be such that all parts are small, each part is connected, and if the graph has certain properties, the total number of edges between parts is at most $\epsilon |V|$. In joint work with Dana Ron, we give a partition oracle for graphs with excluded minors whose query complexity is quasi-polynomial in $1/\epsilon$, improving on the result of Hassidim et al. (Proceedings of FOCS 2009), who gave a partition oracle with query complexity exponential in $1/\epsilon$. This improvement implies corresponding improvements in the complexity of testing planarity and other properties that are characterized by excluded minors as well as sublinear-time approximation algorithms that work under the promise that the graph has an excluded minor.

In joint work with Dana Ron and Ronitt Rubinfeld, we provide another partition oracle for graphs with excluded minors whose query complexity is only polynomial in $1/\epsilon$. The partition that this oracle provides access to is not guaranteed to have a small number of edges between parts. 

Instead, it is guaranteed that if one contracts each part of the partition into a single vertex, then the resulting graph is sparse (with high probability).

We use this oracle in order to provide an algorithm, which gives an oracle access to a sparse spanning sub-graph of the input graph. This spanning sub-graph has the property that the pairwise distances between vertices are preserved up to a small factor. This property is desirable for many applications, e.g., in the construction of compact routing schemes with small stretch and in distance labeling schemes.