Distinct distances in graph drawings (Q1010836)

Summary: The 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 \({\mathcal 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})\).