이 그래프는 임베딩 가능하고 이름이 있습니까?

Question

나는 2 차원 평면에 무향 그래프를 투사 할되도록 :

1. 유클리드 거리가 단계적으로 거리를 유지 (즉, A와 B 사이의 최단 경로는 C와 D 사이의 최단 거리보다 짧은 경우 다음, A와 B 사이의 유클리드 거리는, 유클리드 거리와 거리 사이의 단계적 최소 차이가 최소화되어 A와 B 사이의 유클리드 거리)

2. 미만이다. 고유 한 최소값이 없으면 이상적으로 솔루션 집합이 생성되거나 설명됩니다.

이것이 가능하지 않은 경우 그래프에서 가능한 최소한의 제약 조건은 무엇입니까? 나는 일반적으로 질문에 흥미가 있지만, 현재는 최소 제거 된 유한 격자를 원한다.

Answer 1

적어도 일반적인 경우에는 첫 번째 요구 사항이 불가능하다고 생각합니다. 모든 경로 길이가 동일한 4 개의 노드로 구성된 완전 연결된 그래프를 고려하십시오. 두 개의 유클리드 공간에서 동일한 속성 (4 개의 일치 지점 제외)을 나타내는 4 개의 점을 선택할 수 없습니다.

일부 유용한 정보는 Diego의 대답을 참조하십시오 (그래프 이론에 대한 지식은 매우 제한적 임).

Answer 2

graph embeddng이라고합니다. theorem that gives an upper limit to the distortion도 있습니다. 가장 좋아하는 퍼가기 알고리즘은 SDE입니다. SDP 라이브러리가있는 경우 모든 언어로 구현하기가 상당히 쉽습니다.

Here 님의 알고리즘이 조금 더 간단합니다.