<p>Many years later, it looks like OP has finally answered his own question: <a href="https://arxiv.org/pdf/1807.01478.pdf" rel="noreferrer">Near-Optimal Distance Emulator for Planar Graphs</a> by Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes, and Oren Weimann was just posted on the arxiv.</p>

<p>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.</p>

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

CC BY-SA 4.0
2018-07-05T16:29:39.650Z
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 張顯之
CC BY-SA 4.0
2018-07-05T13:05:20.547Z
2018-07-05T13:05:20.547Z
GMB
<p>you may want to look at Klein's planar subset spanner, which preserves distances up to a 1+epsilon factor.</p>

<p>A Subset Spanner for Planar Graphs, with Application to Subset TSP
<a href="http://doi.acm.org/10.1145/1132516.1132620" rel="nofollow">http://doi.acm.org/10.1145/1132516.1132620</a></p>

CC BY-SA 3.0
2011-04-25T02:50:19.263Z
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 張顯之
CC BY-SA 3.0
2012-04-26T00:33:02.057Z
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
CC BY-SA 3.0
2011-04-25T02:20:55.860Z
2011-04-25T02:20:55.860Z
Christian Sommer
<p>Let G be an n-node undirected graph, and let T be a node subset of V(G) called <em>terminals</em>.  A <em>distance preserver</em> of (G,T) is a graph H satisfying the property</p>
<p><span class="math-container">$$d_H(u,v) = d_G(u,v)$$</span></p>
<p>for all nodes u, v in T. (Note that H is NOT necessarily a subgraph of G.)</p>
<p>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).</p>
<p><img src="https://i.sstatic.net/8gs0r.jpg" alt="enter image description here" /></p>
<p>Distance preserver with various parameters are known to exist. I'm particularly interested in the one with the following properties:</p>
<ol>
<li>G is planar and unweighted (that is, all edges of G has weight one),</li>
<li>T has size <span class="math-container">$O(n^{0.5})$</span>, and</li>
<li>H has size (the number of nodes and edges) <span class="math-container">$o(n)$</span>. (It would be nice if we have <span class="math-container">$O(\frac{n}{\log\log n})$</span>.)</li>
</ol>
<blockquote>
<p>Does such a distance preserver exist?</p>
</blockquote>
<p>If one cannot meet the above properties, any kind of relaxations are welcomed.</p>
<hr />
<p>References:</p>
<ul>
<li><a href="http://www.cs.yale.edu/%7Eelkin/src.cam_ready.ps" rel="nofollow noreferrer">Sparse Source-wise and Pair-wise Distance Preservers</a>, Don Coppersmith and Michael Elkin, SIDMA, 2006.</li>
<li><a href="http://www.cs.bgu.ac.il/%7Eelkinm/add_sp.jrnl.v2.ps" rel="nofollow noreferrer">Sparse Distance Preservers and Additive Spanners</a>, Béla Bollobás, Don Coppersmith, and Michael Elkin, SIDMA, 2005.</li>
<li><a href="http://www.eecs.umich.edu/%7Epettie/theoryseminar/papers/Thorup-Zwick-sublinear-additive-error.pdf" rel="nofollow noreferrer">Spanners and emulators with sublinear distance errors</a>, Mikkel Thorup and Uri Zwick, SODA, 2006.</li>
<li><a href="https://web.archive.org/web/20110107053409/http://www.almaden.ibm.com/cs/people/dpwoodru/w06b.pdf" rel="nofollow noreferrer">Lower Bounds for Additive Spanners, Emulators, and More</a>, David P. Woodruff, FOCS, 2006.</li>
</ul>
<p>Distance preserver is also known as an <em>emulator</em>; many related work can be found on internet by searching the term <em>spanner</em>, 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.</p>

CC BY-SA 3.0
2011-04-22T20:30:54.373Z
−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
CC BY-SA 3.0
2011-04-23T03:58:09.653Z
@Tsuyoshi: Thanks for the useful tips! I did not know that :)
Hsien-Chih Chang 張顯之
<ds.algorithms><reference-request><graph-algorithms><planar-graphs>
The existence of planar distance preserver?
Hsien-Chih Chang 張顯之
# The existence of planar distance preserver?

(Asked by: username_0 on 2011-04-11)

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

![enter image description here](https://i.sstatic.net/8gs0r.jpg)

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](http://www.cs.yale.edu/%7Eelkin/src.cam_ready.ps), Don Coppersmith and Michael Elkin, SIDMA, 2006.
* [Sparse Distance Preservers and Additive Spanners](http://www.cs.bgu.ac.il/%7Eelkinm/add_sp.jrnl.v2.ps), Béla Bollobás, Don Coppersmith, and Michael Elkin, SIDMA, 2005.
* [Spanners and emulators with sublinear distance errors](http://www.eecs.umich.edu/%7Epettie/theoryseminar/papers/Thorup-Zwick-sublinear-additive-error.pdf), Mikkel Thorup and Uri Zwick, SODA, 2006.
* [Lower Bounds for Additive Spanners, Emulators, and More](https://web.archive.org/web/20110107053409/http://www.almaden.ibm.com/cs/people/dpwoodru/w06b.pdf), 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.

**Tags:** ds.algorithms, reference-request, graph-algorithms, planar-graphs
> **Comments:**
> **username_1**: −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)  
> **username_0**: @Tsuyoshi: Thanks for the useful tips! I did not know that :)  

---

## 2 answers

### Answer by username_2 on 2018-07-05. Score: 5 | Accepted answer

Many years later, it looks like OP has finally answered his own question: [Near-Optimal Distance Emulator for Planar Graphs](https://arxiv.org/pdf/1807.01478.pdf) 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!)

> **Comments:**
> **username_0**: 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 :)  

---

### Answer by username_3 on 2011-04-25. Score: 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>

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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...  

---

