[pointedset]

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 case more dimensions might be helpful for bigger graphs. (With this definition, every graph with n vertices can be untangled in n-1 dimensions, and the complete graph shows that this is a tight bound).

Another generalization is to look at 2-dimensional surfaces of higher genus rather than spaces of higher dimension: something like a donut or a multi-handled donut. There's a whole bunch of research already done on that topic, search for "graph embeddings".

[somewhereoutth]

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.

[pointedset]

Note that for this property, you want edges to be reasonably close, but you also need to say that vertices are reasonably far apart: otherwise you could always get a "less tangled" graph by just shrinking it until it's too small to see.

[layer8]

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.