Can a graph be non-planar in 3d?

Question

I am currently reading Trudeau's introductory book on Graph Theory and have just come across the concept of planar and non-planar graphs. The definition reads: 'A graph is planar if it is isomorphic to a graph that has been drawn in a plane without edge-crossings'. My question is, if the definition is changed slightly, and we replace 'plane' with '3D space', does this lead to all possible finite graphs being planar? Or to put it more simply (I think), is there a graph which cannot be drawn without edge crossings in 3D space? And if not how can one prove that such a graph would not exist?

I apologize if this question is trivial; I thought of graphs only as representations of functions until yesterday.

Answer 1

A finite graph has a finite vertex set $V=\{v_1,v_2,\ldots, v_n\}$. Arrange these vertices as points $v_k=(k,0,0)$ $(1\leq k\leq n)$ on the $x$-axis of ${\mathbb R}^3$. Some pairs $v_i$, $v_j$ $(i\ne j)$ are joined by an edge. Assume there are $N\leq{n\choose2}$ edges. Choose $N$ different planes containing the $x$-axis, and draw each occurring edge $\{v_i,v_j\}$ as a half circle connecting $v_i$ with $v_j$ in one of these planes. The $N$ edges will then not intersect.

By the way: Graphs of functions and graphs studied here have nothing in common. It's a semantic accident that the two completely different things have obtained the same name.

Answer 2

To extend Christian's construction: you can in fact even embed the vertices of your graph in $\mathbb{R}^3$ so that all $N$ edges of the graph are straight lines, and this construction is close to trivial: just make all of the coordinates of the vertices algebraically independent of each other. You can show that this is possible by a dimensionality/counting argument (essentially, given any finite collection of real numbers, there are only countably many numbers in algebraic dependence with them, so there are uncountably many algebraically independent choices that can be made at each step). The key difference between space and the plane here is that while any two non-parallel straight lines will intersect in the plane, lines in space have an additional 'degree of freedom' that means that they need to satisfy certain conditions in order to intersect, and those conditions can be expressed algebraically in terms of the endpoints of segments of the two lines.