# 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?

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! – Joseph O'Rourke Oct 29 '16 at 0:07

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