A existência de preservador de distância planar?

Seja G um gráfico não-direcionado de n nós e T seja um subconjunto de nós de V (G) chamados terminais . Um preservador de distância de (G, T) é um gráfico H que satisfaz a propriedade

para todos os nós u, v em T. (Observe que H NÃO é necessariamente um subgrafo de G.)

Por exemplo, seja G o seguinte gráfico (a) e T sejam os nós na face externa. Então o gráfico (b) é um preservador de distância de (G, T).

Sabe-se que existe um preservador de distância com vários parâmetros. Estou particularmente interessado em um com as seguintes propriedades:

1. G é plano e não ponderado (ou seja, todas as arestas de G têm peso um),
2. T tem tamanho $O(n^{0.5})$ e
3. H tem tamanho (o número de nós e arestas) $o(n)$ . (Seria bom se tivéssemos $O(\frac{n}{\log\log n})$.)

Existe um tal preservador de distância?

Se não for possível atender às propriedades acima, qualquer tipo de relaxamento é bem-vindo.

Referências:

• Preservadores de Distância Esparsas e Parciais, Don Coppersmith e Michael Elkin, SIDMA, 2006.
• Preservadores para distâncias esparsas e chaves inglesas aditivas , Béla Bollobás, Don Coppersmith e Michael Elkin, SIDMA, 2005.
• Chaves inglesas e emuladores com erros de distância sublinear , Mikkel Thorup e Uri Zwick, SODA, 2006.
• Limites inferiores para chaves inglesas aditivas, emuladores e muito mais , David P. Woodruff, FOCS, 2006.

O preservador de distância também é conhecido como emulador ; muitos trabalhos relacionados podem ser encontrados na internet pesquisando o termo chave inglesa , que exige que H seja um subgrafo de G. Mas, em meus aplicativos, também podemos usar outros gráficos, desde que H preserve as distâncias entre T em G.

Muitos anos depois, parece que o OP finalmente respondeu à sua própria pergunta: Emulador de distância quase ideal para gráficos planares de Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes e Oren Weimann acabou de ser publicado no arxiv.

˜ O (n$\widetilde{O}(\min\{t^2, \sqrt{tn}\})$$|T| =: t$$\widetilde{O}(n^{3/4})$$\widetilde{O}(n)$

(Em uma nota menos formal, acho esse resultado realmente incrível. Parabéns!)

convém observar a chave de subconjunto planar de Klein, que preserva distâncias de até um fator de 1 + epsilon.

Chave de subconjuntos para gráficos planares, com aplicação ao subconjunto TSP http://doi.acm.org/10.1145/1132516.1132620