# Generate random graphs that satisfy the triangle inequality

I would like to generate random graphs that might be geometric graphs in some (unknown) dimension. So I would like every triangle in the graph to satisfy the triangle inequality on its (random) edge lengths/weights. I need something akin to the Erdős/Rényi model such as, "The weighted random graph model," but with the triangle geometric constraint.

The earlier MO question, "Probability that random weights on $K_n$ satisfy triangle inequality," seems quite relevant, but I don't immediately see how it leads to a method for generating the random graphs I need.

So my question is:

Q. How can one generate random Erdős/Rényi weighted graphs that satisfy the triangle inequality for every triangle in the graph?

## 3 Answers

I am not sure I understand the issues: First you generate an ER (or your favorite model) random graph. The constraints that the edge lengths are in $[0, 1]$ and satisfy all possible triangle inequalities defines a polytope in $\mathbb{R}^E,$ and you are just trying to find a uniform random point in the polytope, which is a well-studied problem, see, e.g. Uniformly Sampling from Convex Polytopes

• Brilliant reformulation, Igor! Oct 29 '16 at 0:07

I would generate random graph and discard the longest sides in each n-gon violating the inequality.

let $$|e_{ij}|$$ denote the length of the edge adjacent to vertices $$i$$ and $$j$$, then subtracting $$\Delta^*:=\min\limits_{\lbrace i,j,k\rbrace}\left|e_{ik}\right|+\left|e_{kj}\right|-\left|e_{ij}\right|$$ from every edge-weight renders the resulting graph metric and preserves the variance of the edge-weights.