Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

See, we can divide graphs into planar ones and non-planar ones. This seems to make a lot of sense until you find that this seems to only work in two dimensions.

I can't think of any graph that cannot have a projection in three-dimensional space without any lines intersecting. Obviously, there are non-planar (in the 2d sense) graphs, such as the Petersen graph, but AFAIK it is very easy to make a 3D Petersen graph without any lines intersecting.

What is so special about 2 dimensions that allows nontrivial planar and non-planar graphs? In one dimension all nontrivial graphs are non-"linear", and it seems all three-dimensional graphs are "spacear".

share|improve this question
4  
The equivalent in 3D, I guess, would be to augment the vertices and edges of graphs with faces, and to ask when the faces of a graph don't intersect. –  user7530 Jul 17 '13 at 0:42
    
Among other places, planar graphs come up in the design of integrated circuits. And then there is the long-famous four-colour problem that may have focused more interest on planar graphs than they deserve. –  André Nicolas Jul 17 '13 at 0:48
3  
If you remove a (topological) circle from the plane, it becomes disconnected. If you remove a (topological) circle from a higher-dimensional space, it remains (path-)connected. In dimensions $> 2$ you can always wiggle a little to avoid the edges you already have. –  Daniel Fischer Jul 17 '13 at 0:48
2  
Planar graphs form one of the smallest minor-closed classes of graphs, and would probably be important for this reason alone, even without the four-color problem. It is true that any finite graph can be imbedded in 3-space without any edges crossing. But we can the consider which graphs have linkless embeddings in 3-space - embeddings where no pair of cycles is linked. So even in three dimensions there are interesting questions. –  Chris Godsil Jul 17 '13 at 1:17

1 Answer 1

There is a theorem of Dimension Theory which says that an $n$-dimensional thingie (where thingie = separable metric space) can always be embedded in $(2n+1)$-dimensional Euclidean space; some of them require the full $2n+1$ dimensions, others can be embedded in lower-dimensional Euclidean spaces. A (linear) graph is $1$-dimensional, so all graphs can be embedded in $3$D space, some in $2$D, and a very few in $1$D.

If you want to learn about dimension theory, I can recommend a very nice and readable book from 1948, Dimension Theory by Witold Hurewicz and Henry Wallman. The prerequisite is a course in general topology.

Getting back to graphs, someone might quibble that a "graph" with more than $2^{\aleph_0}$ vertices can't be embedded in $\mathbb R^3$. I assume that we're talking about finite or countable graphs, which are separable metric spaces. Actually any (simple) graph with at most continuum-many vertices has a straight-line embedding (edges are straight line segments) in $\mathbb R^3$. Namely, map the vertices of the graph to distinct points on the twisted cubic curve $x=t,y=t^2,z=t^3$; it's easy to see that the straight line segments with endpoints on that curve do not intersect one another.

share|improve this answer
    
How could I show that a finite graph is a separable metric space? –  Brent J Nov 8 '13 at 4:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.