Die Existenz von Planar Distance Preserver?

Sei G ein ungerichteter Graph mit n Knoten und sei T eine Knotenuntermenge von V (G), die Terminals genannt wird . Ein Entfernungsbewahrer von (G, T) ist ein Graph H, der die Eigenschaft erfüllt

für alle Knoten u, v in T. (Beachten Sie, dass H NICHT unbedingt ein Teilgraph von G ist.)

Zum Beispiel sei G der folgende Graph (a) und T die Knoten auf der Außenseite. Dann ist Graph (b) ein Distanzbewahrer von (G, T).

Distanzspeicher mit verschiedenen Parametern sind bekannt. Ich interessiere mich besonders für die mit den folgenden Eigenschaften:

1. G ist planar und ungewichtet (dh alle Kanten von G haben Gewicht eins),
2. T hat die Größe und$O(n^{0.5})$
3. H hat die Größe (die Anzahl der Knoten und Kanten) . (Es wäre schön, wenn wir O ( $o(n)$.)$O(\frac{n}{\log\log n})$

Gibt es einen solchen Distanzhalter?

Wenn man die oben genannten Eigenschaften nicht erfüllen kann, ist jede Art von Entspannung willkommen.

Verweise:

• Sparse Source-weise und Pair-weise Distance Preservers , Don Coppersmith und Michael Elkin, SIDMA, 2006.
• Sparse Distance Preservers und Additive Schraubenschlüssel , Béla Bollobás, Don Coppersmith und Michael Elkin, SIDMA, 2005.
• Schraubenschlüssel und Emulatoren mit sublinearen Abstandsfehlern , Mikkel Thorup und Uri Zwick, SODA, 2006.
• Untere Schranken für Additive Schraubenschlüssel, Emulatoren und mehr , David P. Woodruff, FOCS, 2006.

Distance Preserver wird auch als Emulator bezeichnet . Viele verwandte Arbeiten finden Sie im Internet, indem Sie nach dem Begriff spanner suchen , für den H ein Teilgraph von G sein muss. In meinen Anwendungen können wir jedoch auch andere Graphen verwenden, sofern H die Abstände zwischen T in G beibehält.

Viele Jahre später scheint OP endlich seine eigene Frage beantwortet zu haben: Nahezu optimaler Entfernungsemulator für planare Graphen von Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes und Oren Weimann wurde gerade auf arxiv veröffentlicht.

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

(Weniger formal finde ich dieses Ergebnis wirklich erstaunlich. Herzlichen Glückwunsch!)

Vielleicht möchten Sie sich Kleins Schlüssel für planare Teilmengen ansehen, der Entfernungen bis zu einem Faktor von 1 + epsilon beibehält.

Ein Teilmengenschlüssel für ebene Graphen mit Anwendung auf die Teilmenge TSP http://doi.acm.org/10.1145/1132516.1132620