14
$\begingroup$

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

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ −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) $\endgroup$ – Tsuyoshi Ito Apr 22 '11 at 20:30
  • $\begingroup$ @Tsuyoshi: Thanks for the useful tips! I did not know that :) $\endgroup$ – Hsien-Chih Chang 張顯之 Apr 23 '11 at 3:58
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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 :) $\endgroup$ – Hsien-Chih Chang 張顯之 Jul 5 '18 at 16:29
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Hsien-Chih Chang 張顯之 Apr 25 '11 at 2:50
  • $\begingroup$ 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... $\endgroup$ – Christian Sommer Apr 26 '12 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.