# Approximate euclidean graph from distance matrix?

In a personal project of mine, I have been faced with the following problem. I have an $$n \times n$$ matrix $$T$$ where an entry $$t_{ij} \geq 0$$ denotes an arbitrary metric between two points $$i$$ and $$j$$ in the 2D Euclidean space.

What I would like to do is create a graph $$G=(V,A)$$ which can approximate matrix $$T$$ where $$|V|=n$$. The goal is to assign coordinates $$(x_i,y_i)$$ for each point $$i \in V$$. This should be done in such a way that the Euclidean distance $$d_{ij}$$ between $$i,j \in V$$ defined as

$$d_{ij} = \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}$$

should approximate $$t_{ij}$$ as much as possible. Hence:

$$d_{ij} \approx t_{ij}$$

There is one additional constraint: the points need to be placed within a circle of radius $$R$$.

So far I have tried to approach this problem from a mathematical programming point-of-view. Unfortunately, my experience is mostly with linear programming but the problem I have at hand appears to be non-linear. Here is the model I have developed, where $$x_i$$ and $$y_i$$ are real-valued variables.

$$\min \sum_{i \in V}\sum_{j \in V}|d_{ij}-t_{ij}|$$

$$\text{s.t. }$$

$$d_{ij} = \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}$$

$$d_{0j} \leq R,\ \forall\ j \in V,\ \text{0 refers to coordinate } (0,0)$$

$$x_i,y_i \in [-R,R],\ \forall\ i \in V$$

This way we know that an optimal solution would exist when the objective function is exactly 0.

However, I still have open questions which I cannot seem to find the answer to:

1. Is this the best way to model such problem?
2. How can I solve this model? Are there algorithms or solvers (e.g., CPLEX) for such model?
3. Does this problem already exist with some name in the literature?

Can anyone shed some light on this problem?

You could also try adapting force-directed graph drawing to your problem. You have a preferred distance $$t_{ij}$$ between each pair of vertices $$i,j$$, so you can treat this as a spring that exerts a force if its length is larger than $$t_{ij}$$ or smaller than $$t_{ij}$$.