Subdividing a graph toward a unit-distance graph in the plane (Q1971803): Difference between revisions

What is the least number \(\text{sd}(G)\) of vertices to be added to the edges of a graph \(G\), so as to be able to imbed it in the plane with only unit length segments as edges? This subdivision number is studied for complete and complete bipartite graphs. The following bounds are obtained: \(\frac{1}{2}n(n-1) - t(n) \leq \text{sd}(K_n) \leq \frac{1}{2}(n-2)(n-3)+2\), where \(t(n)\) is the largest number of edges of a 4-cycle-less graph on \(n\) vertices; and \(\text{sd}(K(m,n))= (m-1)(n-m) \) when \(n \geq m(m-1)\). Tables of exact values are derived for small values of \(n\) and \(m\).