Earlier quoted context omitted.
Yes, if "untangled" means "no edge crossings", then 3 dimensions is enough for any graph to be untangled. As a proof, you can put the vertices at coordinates (0, 0, 0), (1, 1, 1), (2, 4, 8), (3, 9, 27), ..., (n, n^2, n^3), and then no two edges will cross. A different definition of "untangled" might be that all edges have roughly the same length (which could be formally defined in lots of different ways), in which ca…
Ah indeed. I was meaning 'untangled' in the looser sense of 'can be spread out over 3D space with most/all connected points reasonably close to each other'. Seems like this is a topological property, that the 'neighbourhoods' defined by the connections 'tessellate' in some sense.
You can place all n vertices within a unit sphere, with a roughly uniform distribution. Then the distance between two vertices is at most 2 and at least roughly around the cubic root of 4π/3n (sphere volume divided by number of vertices). So the maximum factor between edge lengths in that construction is proportional to the cubic root of n. I would suspect that it’s possible to construct graphs where that factor cannot be significantly improved upon.