Adanya pemelihara jarak planar?

Misalkan G adalah grafik nir simpul n-simpul, dan misalkan T adalah subset simpul dari V (G) yang disebut terminal . Pemelihara jarak (G, T) adalah grafik H yang memuaskan properti

untuk semua node u, v dalam T. (Perhatikan bahwa H TIDAK harus merupakan subgraph dari G.)

Sebagai contoh, misalkan G menjadi grafik berikut (a) dan T menjadi simpul pada permukaan eksternal. Kemudian grafik (b) adalah pemelihara jarak (G, T).

Pemelihara jarak dengan berbagai parameter diketahui ada. Saya sangat tertarik dengan properti berikut:

1. G adalah planar dan tidak berbobot (yaitu, semua tepi G memiliki bobot satu),
2. T memiliki ukuran $O(n^{0.5})$ , dan
3. H memiliki ukuran (jumlah node dan tepi) . (Alangkah baiknya jika kita memiliki .)$o(n)$$O(\frac{n}{\log\log n})$

Apakah pemelihara jarak seperti itu ada?

Jika seseorang tidak dapat memenuhi properti di atas, segala jenis relaksasi disambut.

Referensi:

• Preservers Sumber-bijaksana dan Pasangan-bijaksana Jarak , Don Coppersmith dan Michael Elkin, SIDMA, 2006.
• Pengawet Jarak Jarang dan Kunci Tambahan , Béla Bollobás, Don Coppersmith, dan Michael Elkin, SIDMA, 2005.
• Kunci pas dan emulator dengan kesalahan jarak sublinear , Mikkel Thorup dan Uri Zwick, SODA, 2006.
• Batas Bawah untuk Spanduk Aditif, Emulator, dan Lainnya , David P. Woodruff, FOCS, 2006.

Pemelihara jarak juga dikenal sebagai emulator ; banyak pekerjaan terkait dapat ditemukan di internet dengan mencari istilah spanner , yang mengharuskan H untuk menjadi subgraph dari G. Tetapi dalam aplikasi saya, kami dapat menggunakan grafik lain juga, selama H mempertahankan jarak antara T di G.

Bertahun-tahun kemudian, sepertinya OP akhirnya menjawab pertanyaannya sendiri: Emulator Jarak Dekat-Optimal untuk Grafik Planar oleh Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes, dan Oren Weimann baru saja diposting di arxiv.

$\widetilde{O}(\min\{t^2, \sqrt{tn}\})$$|T| =: t$$\widetilde{O}(n^{3/4})$$\widetilde{O}(n)$ ; Saya akan sangat curiga bahwa faktor log dalam ukuran dapat dihapus jika kita hanya peduli tentang keberadaan dan bukan waktu perhitungan pemelihara, tetapi saya belum memverifikasi ini dengan seksama.

(Dengan catatan yang kurang formal, saya menemukan hasil ini sangat luar biasa. Selamat!)

Anda mungkin ingin melihat spanner subset planar Klein, yang menjaga jarak hingga faktor 1 + epsilon.

Subset Spanner untuk Grafik Planar, dengan Aplikasi untuk Subset TSP http://doi.acm.org/10.1145/1132516.1132620