Существование планарного расстояния?

14

Пусть G будет ненаправленным графом из n узлов, и пусть T будет подмножеством узлов V (G), называемых терминалами . Сохранитель расстояния (G, T) - это граф H, удовлетворяющий свойству

dЧАС(U,v)знак равноdграмм(U,v)

для всех узлов u, v в T. (Обратите внимание, что H НЕ обязательно является подграфом G.)

Например, пусть G - следующий граф (a), а T - узлы на внешней грани. Тогда граф (b) является сохранителем расстояния (G, T).

введите описание изображения здесь

Известно, что сохранитель расстояния с различными параметрами существует. Я особенно заинтересован в одном со следующими свойствами:

  1. G плоская и невзвешенная (то есть все ребра G имеют вес один),
  2. T имеет размер иО(N0,5)
  3. H имеет размер (количество узлов и ребер) . (Было бы хорошо, если бы у нас было .)о(N)О(NжурналжурналN)

Существует ли такой сохранитель расстояния?

Если вы не можете встретить вышеупомянутые свойства, приветствуются любые виды релаксации.


Ссылки:

Сохранитель расстояния также известен как эмулятор ; многие связанные работы можно найти в Интернете, выполнив поиск по термину « гаечный ключ» , который требует, чтобы H был подграфом G. Но в моих приложениях мы можем использовать и другие графики, если H сохраняет расстояния между T в G.

Сянь-Чжи Чан 張顯 之
источник
-1 для использования JPEG для этого вида рисунка! (просто шучу, но PNG обычно намного лучше как по качеству изображения, так и по размеру файла для простых рисунков)
Tsuyoshi Ito
@Tsuyoshi: Спасибо за полезные советы! Я не знал, что :)
Сянь-Чи Чан 之

Ответы:

4

Спустя много лет, похоже, OP наконец-то ответил на свой вопрос: почти -оптимальный эмулятор расстояний для плоских графиков Сянь-Чжи Чанга, Павла Гавриховского, Шая Мозеса и Орен Вейманн только что был размещен на arxiv.

О~(мин{T2,TN})|T|знак равноTО~(N3/4)О~(N)

(На менее формальной ноте я нахожу этот результат действительно удивительным. Поздравляю!)

GMB
источник
1
Спасибо @GMB за публикацию в качестве ответа. Небольшой улов здесь в том, что хранитель направлен ; остается открытым вопрос, существует ли ненаправленный (но все же не обязательно плоский) эмулятор сублинейного размера. Но очень приятно наконец узнать ответ на старый вопрос после всех этих лет :)
Сянь-Чи Чанг Chang 之
2

Вы можете посмотреть на плоский гаечный ключ Кляйна, который сохраняет расстояния до 1 + эпсилон-фактор.

Гаечный ключ подмножества для плоских графов с приложением к подмножеству TSP http://doi.acm.org/10.1145/1132516.1132620

Кристиан Соммер
источник
Спасибо, я прочитал газету, и есть разрыв между его конструкцией и нашими требованиями. Кажется, что любой гаечный ключ не будет работать, пока он является подграфом исходного графа; в качестве контрпримера можно взять график сетки. Но есть эмуляторы для графиков сетки.
Сянь-Чжи Чан 25 之
другая идея строительства, может быть, это работает? 1) рекурсивно применять разделители кратчайшего пути (Thorup, FOCS'01) 2) eps-cover для каждой вершины [первые два шага строят метки расстояния] есть sqrt {n} терминалов, каждый с меткой размера O (log n / eps), соединяясь с общим числом не более чем sqrt {n} * log n путей и 1 / eps раз больше порталов 3) сокращать порталы на путях с помощью взвешенных ребер и сокращать соединения с порталами по ребрам, итоговый граф должен иметь примерно sqrt {n} * записывает n вершин и ребер (до eps) и представляет 1 + eps кратчайших путей для точных расстояний, которые я не знаю ...
Кристиан Соммер