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.



How to show that random graphs cannot be embedded with short edges
Perhaps you could look into [Spectral Graph Drawing](http://www.cs.yale.edu/homes/spielman/561/2015/lect02-15.pdf).


Since a single comment with a link does not qualify as an answer in the views of many on this site, and truly I don't have enough reputation to just post a comment, let me try to expand on this post to help myself learn what is considered sufficient material for an answer.


Spectral Graph Drawing is a technique that uses eigenvectors (usually those of small eigenvalues) of the graph's Laplacian matrix as Euclidean coordinates of plotted vertices. The Laplacian matrix of graph $G=(V,E)$,
$$
 L\_{ij}=D\_{ii}-A\_{ij}
$$
($i,j\in[1,\vert V\vert]$), is formed by subtracting the adjacency matrix from a diagonal matrix whose elements are the degrees of each vertex.


I don't think there is a strict standard on exactly how the coordinates are derived from the eigenvectors. But a brief Google search reveals a common method is to derive coordinates in $\mathbb{R}^2$ from the 2 eigenvectors of the 2 smallest eigenvalues. The $(x,y)$ coordinates of the $k^\mathrm{th}$ vertex will be the $k^\mathrm{th}$ elements of those eigenvectors respectively. In this example method, one can see that a vertex $v$'s coordinate is related to an average of those of its neighbors ($u$'s):
$$
\delta\_v\cdot x(v)=\sum\limits\_{(u,v)\in E}x(u)+\lambda x(v)\\
x(v)=\mathrm{E}[x(u)]\frac{\delta\_v}{\delta\_v-\lambda}=\mathrm{E}[x(u)](1+\frac{\lambda}{\delta\_v-\lambda})
$$
where $\delta\_v$ is the degree of vertex $v$ and $\lambda$ is the eigenvalue corresponding to the eigenvector represented in the equation above (of its vertex $v$ element). $\mathrm{E}[\cdot]$ is the arithmetic mean. So intuitively, the "variance" is small when the mean is close to $0$ (i.e. neighbors are evenly placed around the origin) and when $\lambda$ is small compared to $\delta\_v$.


The high level sense from easily searchable literature on this topic suggests the issues about how to constrain "fair" embedding as discussed in the comments are addressed in the current art of using Spectral Graph Drawing. The suggested *unorderedness* metric in the question can be computed from Euclidean distances between the produced coordinates.


I guess the intention of the metric was to measure whether many edges has to be drawn across almost the diameter of the plot. The simple intuitive analysis above shows the Spectral Graph Drawing method inherently tries to minimize such long edges, so it may be a great match for the purpose. Spielman showed examples in a recent [video](https://youtu.be/CDMQR422LGM?t=1488). It is worth watching in whole for a great overview of Spectral Graph Drawing.


There is also related research on the graph Laplacian in the context of [random graphs](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.420.2735) and ["entropy"](https://arxiv.org/abs/1809.07533).


Finally, I believe it is already known that random graphs will not result in good pictures from Spectral Graph Drawing. If the input signal is noise-like, linear operations will not introduce information. At best, maybe one could introduce a relation between a metric of the plot based on a certain drawing method, and the number of vertices and edges of a random graph.


