\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Paz Carmi, Vida Dujmovi\'{c}, Pat Morin and David R.~Wood}
%
%
\medskip
\noindent
%
%
{\bf Distinct Distances in Graph Drawings}
%
%
\vskip 5mm
\noindent
%
%
%
%
The {\em distance-number} of a graph $G$ is the minimum number of
distinct edge-lengths over all straight-line drawings of $G$ in the
plane. This definition generalises many well-known concepts in
combinatorial geometry. We consider the distance-number of trees,
graphs with no $K^-_4$-minor, complete bipartite graphs, complete
graphs, and cartesian products. Our main results concern the
distance-number of graphs with bounded degree. We prove that
$n$-vertex graphs with bounded maximum degree and bounded treewidth
have distance-number in ${\cal O}(\log n)$. To conclude such a
logarithmic upper bound, both the degree and the treewidth need to be
bounded. In particular, we construct graphs with treewidth $2$ and
polynomial distance-number. Similarly, we prove that there exist
graphs with maximum degree $5$ and arbitrarily large
distance-number. Moreover, as $\Delta$ increases the existential lower
bound on the distance-number of $\Delta$-regular graphs tends to
$\Omega(n^{0.864138})$.


\bye

.