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

Question

Я хочу спроецировать неориентированный граф на 2-мерную плоскость так, чтобы:

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

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

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

Answer 1

Это называется graph embeddng . Есть даже теорема , которая дает верхний предел искажения . Алгоритм встраивания, который мне нравится больше всего, это SDE . Это довольно легко реализовать на любом языке, если у вас есть библиотека SDP .

Здесь алгоритм, который немного проще.

Answer 2

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

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