Minimal Distinct Lengths in Complete Graphs

69 Views Asked by At

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.

graphs with few distinct lengths

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

1

There are 1 best solutions below

0
On BEST ANSWER

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:

Point sets in Euclidean space with a small number of distinct distances

Erdős distance problem n=12