La existencia de preservador de distancia plana?

Sea G un gráfico no dirigido de n-nodos, y sea T un subconjunto de nodos de V (G) llamados terminales . Un preservador de distancia de (G, T) es un gráfico H que satisface la propiedad

para todos los nodos u, v en T. (Tenga en cuenta que H NO es necesariamente un subgrafo de G.)

Por ejemplo, sea G el siguiente gráfico (a) y T los nodos en la cara externa. Entonces el gráfico (b) es un preservador de distancia de (G, T).

Se sabe que existe un preservador de distancia con varios parámetros. Estoy particularmente interesado en el que tiene las siguientes propiedades:

1. G es plano y no ponderado (es decir, todos los bordes de G tienen un peso uno),
2. $O(n^{0.5})$
3. $o(n)$$O(\frac{n}{\log\log n})$

¿Existe tal preservador de distancia?

Si uno no puede cumplir con las propiedades anteriores, cualquier tipo de relajación es bienvenida.

Referencias

• Preservadores de distancia dispersos de fuente y pareja , Don Coppersmith y Michael Elkin, SIDMA, 2006.
• Preservadores de poca distancia y llaves aditivas , Béla Bollobás, Don Coppersmith y Michael Elkin, SIDMA, 2005.
• Llaves y emuladores con errores de distancia sublineales , Mikkel Thorup y Uri Zwick, SODA, 2006.
• Límites más bajos para llaves aditivas, emuladores y más , David P. Woodruff, FOCS, 2006.

El preservador de distancia también se conoce como emulador ; se puede encontrar mucho trabajo relacionado en Internet buscando el término llave inglesa , que requiere que H sea un subgrafo de G. Pero en mis aplicaciones también podemos usar otros gráficos, siempre que H conserve las distancias entre T en G.

Muchos años después, parece que OP finalmente ha respondido a su propia pregunta: Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes y Oren Weimann acaban de publicar en el arxiv su emulador de distancia casi óptima para gráficos planos.

$\widetilde{O}(\min\{t^2, \sqrt{tn}\})$$|T| =: t$$\widetilde{O}(n^{3/4})$$\widetilde{O}(n)$ tiempo; Sospecharía firmemente que los factores de registro en el tamaño pueden eliminarse si solo nos preocupamos por la existencia y no por el tiempo de cálculo del preservador, pero no lo he verificado rigurosamente.

(En una nota menos formal, encuentro este resultado realmente sorprendente. ¡Felicidades!)

es posible que desee ver la llave de subconjunto planar de Klein, que conserva las distancias hasta un factor de épsilon de 1 +.

Una llave de subconjunto para gráficos planos, con aplicación al subconjunto TSP http://doi.acm.org/10.1145/1132516.1132620