# The existence of planar distance preserver?

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:

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.

• −1 for using JPEG for this kind of figure! (just joking, but PNG is usually much better in both image quality and file size for simple figures) – Tsuyoshi Ito Apr 22 '11 at 20:30
• @Tsuyoshi: Thanks for the useful tips! I did not know that :) – Hsien-Chih Chang 張顯之 Apr 23 '11 at 3:58

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!)

• Thank you @GMB for posting it as an answer. A small catch here is that the preserver is directed; it is an open question whether an undirected (but still not necessarily planar) emulator of sublinear-size exists. But it is quite satisfying to finally know the answer to an old question after all these years :) – Hsien-Chih Chang 張顯之 Jul 5 '18 at 16:29

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

• Thanks, I've read the paper, and there's a gap between his construction and our requirements. It seems that any spanner won't work as long as it is a subgraph of the original graph; one can take a grid graph as a counter-example. But there are emulators for the grid graphs. – Hsien-Chih Chang 張顯之 Apr 25 '11 at 2:50
• another construction idea, maybe it works? 1) recursively apply shortest-path separators (Thorup, FOCS'01) 2) eps-cover for each vertex [first two steps construct distance labels] there are sqrt{n} terminals, each with a label of size O(log n / eps), connecting to a total number of at most sqrt{n}*log n paths and 1/eps times more portals 3) shortcut the portals on paths by weighted edges and shortcut the connections to portals by edges the resulting graph should have roughly sqrt{n}*log n vertices and edges (up to eps) and represent 1+eps shortest paths for exact distances I don't know... – Christian Sommer Apr 26 '12 at 0:33