4 ms·
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'. Se
by somewhereoutth 4y ago
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 4y agoNote 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.
- deleted 4y ago[deleted]
- layer8 4y agoYou 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.