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:
- G is planar and unweighted (that is, all edges of G has weight one),
- T has size $O(n^{0.5})$, and
- 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.