2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ivan Neretin Oct 28 '16 at 21:58
2
$\begingroup$

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

$\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.