3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Brilliant reformulation, Igor! $\endgroup$ – Joseph O'Rourke Oct 29 '16 at 0:07
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.