0

Say you have a graph drawn out in 2D space, but some of the edges cross, and there's no way to arrange the edges so that there are no crossings in 2D. It happens that, by moving the graph into 3D, you may be able to rearrange the edges so that they don't cross.

  1. By increasing the dimension of the space by $1$, are you guaranteed to have no crossings?
  2. If not, then how can you go about finding the minimum dimension of space in which the edges don't cross?
Archie Gertsman
  • 1,051
  • Every graph can be embedded in three dimensional space without self intersections. – Matt Samuel Oct 19 '19 at 22:54
  • Every simple graph with at most $2^{\aleph_0}$ number of vertices can be embedded in $\mathbb{R}^3$ using straight line segment as edges. For a proof for the case with finite number of vertices, see here – achille hui Oct 19 '19 at 22:55

0 Answers0