For each (not necessarily planar) embedding of a graph in $\mathbb{R}^k$ one can calculate the ratio

$$\gamma = \frac{\textsf{mean Euclidean length of edges}}{\textsf{mean Euclidean distance between nodes}} \times \textsf{diameter}$$

where the diameter is the maximal Euclidean distance between nodes. An embedding consists in giving each node of the graph an arbitrary position under the restriction that the minimal Euclidean distance between nodes is 1, and drawing straight lines between adjacent nodes. Note, that such an embedding in general is not planar, and is not supposed to be.

Call $\gamma$ the $k$-unorderedness of the embedding. The $k$-unorderedness of a graph is the minimal unorderedness of its embeddings in $\mathbb{R}^k$. The unorderedness of a graph is its minimal $k$-unorderedness.

For a 10x10 square grid in the natural embedding in $\mathbb{R}^2$, the mean distance is $\approx$ 5.19 while the mean length of edges is 1. This gives – with diameter $\sqrt{200}$ – supposedly $\gamma \approx$ 2.69 for this graph (which would have to be proved but this seems not to be hard).

I wonder how to **determine $\gamma$ for a given (Erdös-Renyi) random graph**? One obviously cannot check all of its embeddings, and one cannot - as in the case of the square grid - start with a natural guess and prove that it is the best case. So how would I proceed?

What might be a **lower bound** $\gamma_0$ such that almost all graphs have $\gamma > \gamma_0$?

What would be even more enlightening: To know the expected **distribution of edge lengths** for $\gamma$-minimal embeddings of random graphs (in units of mean mode distance). How would I guess it? Can it be shown from first principles that it will be a Poisson distribution (like the degree distribution)? Or possibly a scale-free distribution? For the square grid we know the distribution: it's a delta peak at 1.

15more comments