Возможно ли это вложение графа и имеет ли оно имя?

Question

Хочу спроектировать неориентированный граф в 2d плоскости таким образом, что:

1. расстояние евклидовой сохраняет ступенчатое расстояние (т.е., если самый короткий путь между А и В меньше, чем самый короткий путь между С и D , то расстояние евклидовой между а и в меньше, чем расстояние евклидовой между а и в)

2. минимальная разница между расстоянием евклидова и ступенчатого расстоянии минимизируется. В идеале набор решений генерируется или описывается, если нет единственного минимума.

Если это невозможно, каковы минимальные наборы ограничений на графике, которые делают это возможным? Меня интересует вопрос вообще, хотя в данный момент я хочу его для конечной решетки с минимальным удалением.

Answer 1

Я думаю, что первое требование невозможно, по крайней мере, для общего случая. Рассмотрим полностью связанный граф, состоящий из четырех узлов, причем все длины пути равны. Невозможно выбрать четыре точки в двумерном евклидовом пространстве, которые обладают тем же свойством (кроме 4 совпадающих точек).

См. Ответ Диего за полезную информацию (мои знания теории графов очень ограничены!).

Answer 2

Это называется graph embeddng. Там даже есть theorem that gives an upper limit to the distortion. Наиболее подходящим алгоритмом внедрения я считаю SDE. Его довольно легко реализовать на любом языке, если у вас есть библиотека SDP.

Here - алгоритм, который немного проще.