Algorithm to detect planar decorated graphs Consider a finite, non oriented graph $\Gamma$ in which each edge is labelled by a real number.
I say that $\Gamma$ is planar if I can realize it in $\mathbb{R}^2$ in a way that $d(v_i,v_j) =$ label on the edge $ij$ and edges do not cross.
Similarly I say it is spatial if I can embed it in $\mathbb{R}^3$.
Q:


*

*Can you exhibit an algorithm that decides if a given $\Gamma$ is planar? 

*What about spatiality?

*Is such a graph even embeddable into $\mathbb{R}^n$ of a suitable $n$?



Motivation: A doctor wants to represent illnesses. Each vertex is a symptom, the label on the edge $ij$ is $\frac{1}{p_{ij}}$, where $p_{ij}$ is a statistical probability that symptom $i$ and symptom $j$ occur together. In this big picture, illnesses are clans of vertices in the graph, and one could use this representation to detect new syntomps of existing illnesses, or new illnesses by the nearness of some vertices.
 A: Here's a summary of answers to this MathOverflow question.
First of all, your edge-labeled graph $\Gamma$ might not satisfy the triangle inequality. If edge $13$ has a label greater than the sum of the labels on edges $12$ and $23$, then there's no way to embed $\Gamma$ in any metric space; in particular, not $\mathbb R^n$ for any $n$.
So we'll assume that $\Gamma$ is what is called a finite metric space: there are finitely many points (the vertices of $\Gamma$) and positive distances between them (the edge labels) satisfying the triangle inequality. 
Even these are not guaranteed to be embeddable in $\mathbb R^n$ for any $n$. One example is the $4$-vertex graph ($4$-point metric space) below:

Here, any $3$ points are embeddable even in $\mathbb R^1$ just fine, and are forced to lie in a straight line in any $\mathbb R^n$. But you can't put all four in $\mathbb R^n$. This is what is called a non-flat metric space.
The paper Embedding metric spaces in Euclidean space by C.L. Morgan gives conditions for when a finite metric space is flat, and which dimensions it can be embedded into. (This just links to the abstract, which should be accessible to anybody.)
For vertices $x, y, z$ with distances $d(x,y), d(x,z), d(y,z)$ between them, define $\langle x,y,z\rangle = \frac12\left[d(x,y)^2 + d(y,z)^2 - d(x,z)^2\right]$ and let 
$$\operatorname{Vol}_n(x_0, x_1, \dots, x_n) = \frac1{n!} \sqrt{\det \begin{bmatrix}\langle x_0, x_1, x_1\rangle & \langle x_0, x_1, x_2\rangle & \cdots & \langle x_0, x_1, x_n\rangle \\ \langle x_0, x_2, x_1\rangle & \langle x_0, x_2, x_2\rangle & \cdots & \langle x_0, x_2, x_n\rangle \\ \vdots & \vdots & \ddots & \vdots \\ \langle x_0, x_n, x_1\rangle & \langle x_0, x_n, x_2\rangle & \cdots & \langle x_0, x_n, x_n\rangle\end{bmatrix}}$$
This is, I think, a variation of the Cayley-Menger determinant which gives the $n$-dimensional volume of the polytope formed by $n+1$ points, in terms of only the distances between them. For $n=2$, this should reduce to Heron's formula for the area of a triangle.
Anyway, the conditions in the paper are that:


*

*If, for any $n+1$ vertices $x_0, x_1, \dots, x_n$ of $\Gamma$, $\operatorname{Vol}_n(x_0, x_1, \dots, x_n)$ isn't real (because it takes a square root of a negative number) then $\Gamma$ isn't flat, so it's not embeddable in $\mathbb R^n$ for any $n$.

*Otherwise, we can embed $\Gamma$ in $\mathbb R^n$ if there is no $(n+1)$-dimensional volume (for $n+2$ vertices of the graph) which is positive.

