5

We call a planar graph one that we can draw in two-space such that no two edges intersect. I was told that we're not so interested in drawing graphs in three-space, because it is "intuitively obvious" that we can just arrange the points and edges in a non-intersecting way because three-space gives us a great deal of room for arrangement.

While I agree that it seems intuitively true, I don't think it's necessarily true: it seems to me as if it might be possible to create a graph for which we cannot conceive a planar realization in three dimensions. If not, can we develop a formal proof that all graphs have a planar realization in three-space?

Newb
  • 17,672
  • 13
  • 67
  • 114
  • 6
    I think you can take any line in the space, and all the planes that contain that line. Then you can put the vertices in the line, and draw each edge in a different plane. – alejopelaez Nov 26 '13 at 00:00
  • It is easy to see that any graph with no more than $\frak c$ vertices can be drawn with straight-line edges already in $\Bbb R^3$ without crossings, because any placement of its vertices with no four at one plane generates such a drawing. – Alex Ravsky Nov 02 '17 at 09:28

1 Answers1

6

First off, "planar realization in three-space" doesn't make much sense; the word "planar" means "in the plane", i.e., in two-space.


Yes, any (simple) graph can be realized in three-space, with the edges represented as nonintersecting straight line segments. You can do that by putting all the vertices on the twisted cubic curve $x=t,y=t^2,z=t^3$. Well, that works for any finite graph; for an infinite graph you need to assume that the vertex set has cardinality at most $2^{\aleph_0}$.

Proof. If there are two crossing edges with endpoints on that curve, then the endpoints are four coplanar points on the curve. Call the points $(t_i,t_i^2,t_i^3),\ i=1,2,3,4,$ where $t_1,t_2,t_3,t_4$ are distinct real numbers, and suppose they all lie on a plane $A+Bx+Cy+Dz=0$ where $A,B,C,D$ are not all zero. Then $A,B,C,D$ satisfy the equation $$\left[\begin{matrix}1&t_1&t_1^2&t_1^3\\1&t_2&t_2^2&t_2^3\\1&t_3&t_3^2&t_3^3\\1&t_4&t_4^2&t_4^3\end{matrix}\right]\left[\begin{matrix}A\\B\\C\\D\end{matrix}\right]=\left[\begin{matrix}0\\0\\0\\0\end{matrix}\right].\tag1$$ However, since the coefficient matrix is a nonsingular Vandermonde matrix, the equation (1) has no nontrivial solution.


If you don't require a straight-line embedding, you can use the construction in the comment by alejopelaez, which also works for graphs with loops and multiple edges. Straight-line embeddings, of course, are only possible for simple graphs.

bof
  • 78,265
  • 2
    I would really like elaboration (or a picture) for the finite graph proof; just saying "Yeah, just put the vertices on this (seemingly arbitrary) curve" isn't very satisfactory. – BlueBomber Jul 03 '14 at 18:23
  • here's an interactive picture for $K_5$ https://www.math3d.org/f9wux3xx – ho boon suan May 26 '21 at 07:50