# Minimal Distinct Lengths in Complete Graphs

Normally, complete graph $K_n$ is drawn as a regular $n$-gon with all diagonals, or a $n-1$-gon with an added point at the center. Occasionally a grid will be used.

Most of the time, the $n$-gon seems to minimize the number of distinct edge lengths. But not always. For example, $K_{12}$ and $K_{19}$ need 6 and 9 distinct lengths in either polygonal form. The below grid-based embeddings need only 5 and 8 distinct lengths.

Are there other solutions that surpass both grid and polygon-based methods?

• Come to think of it, your solutions are also a grid, just a trigonal one. I expect it to be asymptotically better than the rectangular grid. – Ivan Neretin Oct 28 '16 at 21:58

According to the solution of Erdős distinct distances problem, minimal number of distinct edge lengths in a planar (straigh line) drawing of $K_n$ is $\Theta(n/\log n)$. The Wikipeadia page contains many relavant links, so I add only two links to MathOverflow questions: