The existence of planar distance preserver?

Question

Let G be an n-node undirected graph, and let T be a node subset of V(G) called terminals. A distance preserver of (G,T) is a graph H satisfying the property

$$d_H(u,v) = d_G(u,v)$$

for all nodes u, v in T. (Note that H is NOT necessarily a subgraph of G.)

For example, let G be the following graph (a) and T be the nodes on the external face. Then graph (b) is a distance preserver of (G,T).

Distance preserver with various parameters are known to exist. I'm particularly interested in the one with the following properties:

1. G is planar and unweighted (that is, all edges of G has weight one),
2. T has size $O(n^{0.5})$, and
3. H has size (the number of nodes and edges) $o(n)$. (It would be nice if we have $O(\frac{n}{\log\log n})$.)

Does such a distance preserver exist?

If one cannot meet the above properties, any kind of relaxations are welcomed.

---

References:

• Sparse Source-wise and Pair-wise Distance Preservers, Don Coppersmith and Michael Elkin, SIDMA, 2006.
• Sparse Distance Preservers and Additive Spanners, Béla Bollobás, Don Coppersmith, and Michael Elkin, SIDMA, 2005.
• Spanners and emulators with sublinear distance errors, Mikkel Thorup and Uri Zwick, SODA, 2006.
• Lower Bounds for Additive Spanners, Emulators, and More, David P. Woodruff, FOCS, 2006.

Distance preserver is also known as an emulator; many related work can be found on internet by searching the term spanner, which requires H to be a subgraph of G. But in my applications we can use other graphs as well, as long as H preserves the distances between T in G.

Answer 1

Many years later, it looks like OP has finally answered his own question: Near-Optimal Distance Emulator for Planar Graphs by Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes, and Oren Weimann was just posted on the arxiv.

The answer to the original question is yes: it is shown that $\widetilde{O}(\min\{t^2, \sqrt{tn}\})$ edges suffice to preserve distances between $|T| =: t$ terminals, which is optimal up to log factors. In particular $\widetilde{O}(n^{3/4})$ edges suffice for the setting in the OP. This preserver can also be computed in $\widetilde{O}(n)$ time; I would strongly suspect that the log factors in the size can be removed if we care only about existence and not computation time of the preserver, but I have not rigorously verified this.

(On a less formal note, I find this result really amazing. Congrats!)

Answer 2

you may want to look at Klein's planar subset spanner, which preserves distances up to a 1+epsilon factor.

A Subset Spanner for Planar Graphs, with Application to Subset TSP http://doi.acm.org/10.1145/1132516.1132620