6
$\begingroup$

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".

$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$
    – user7530
    Commented Jul 17, 2013 at 0:42
  • $\begingroup$ 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. $\endgroup$
    – André Nicolas
    Commented Jul 17, 2013 at 0:48
  • 3
    $\begingroup$ 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. $\endgroup$
    – Daniel Fischer
    Commented Jul 17, 2013 at 0:48
  • 3
    $\begingroup$ 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. $\endgroup$
    – Chris Godsil
    Commented Jul 17, 2013 at 1:17

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ How could I show that a finite graph is a separable metric space? $\endgroup$
    – Brent J
    Commented Nov 8, 2013 at 4:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .