# Higher dimensional analog to planar graphs?

We usually say that a graph is planar if it can be embedded into 2-space s.t. no edges intersect. Here's a different way to describe the same situation: a graph is planar if it can be embedded into 2-space s.t. the edges form the boundaries of cells which nowhere overlap.

My question: Can you take this second definition and extend the idea to higher dimensions? For instance, allow the cells to be volumes in 3-space - like soap bubbles where the graph edges are the intersection of soap film walls.

-
Intuitively it seems that such "cell" construction would have bounded doubling dimensions, whereas planar graphs can have unbounded doubling dimension –  Yaroslav Bulatov Feb 18 '11 at 21:29

A planar graph is nothing other than a triangulation of the $2$-sphere (via stereographic projection), at least if one allows arbitrary polygons instead of just triangles, so a natural generalization to three dimensions is triangulations of the $3$-sphere where one allows arbitrary (convex) polyhedra instead of just simplices. One can of course talk about triangulations of arbitrary manifolds.

-
When you say "triangulation", do you mean representing vertices of a graph as points in the space? I have trouble imagining how tree structured-graphs fit into this construction –  Yaroslav Bulatov Feb 18 '11 at 21:32
@Yaroslav: yes. See my comment to your answer. If this isn't a good definition for you, pretend I'm actually talking about CW-complexes. –  Qiaochu Yuan Feb 18 '11 at 21:45
I think Qiaochu means tesselating. –  John Berryman Feb 18 '11 at 21:46
... although that might still not be precise here... –  John Berryman Feb 18 '11 at 21:47
Tangent: One of the proofs of Sylvester-Gallai theorem uses this planar graph representation. –  Aryabhata Feb 18 '11 at 22:36

Another generalization is along the genus axis, i.e., consider which graphs can be embedded into a 2d compact surface, such as an $n$-torus. This area is called topological graph theory.

-
That's kind a interesting. –  John Berryman Feb 20 '11 at 4:04
@John: Perhaps a better analog of planar graphs would use geodesic embededdings, not merely topological ones. That is, the edges would be geodesics. I don't know whether topological graph theory handles this nor whether there is a "Riemannian graph theory" out there. I did find the paper "A Riemannian approach to graph embedding", dx.doi.org/10.1016/j.patcog.2006.05.031 , which seems to contains some references for this approach. –  lhf Feb 22 '11 at 11:09
perhaps, but when we start talking about geodesics, we're getting away from the more pure topological questions I was interested in. –  John Berryman Feb 22 '11 at 14:21

I'm not clear about your definition, for a graph below, what are cells and boundaries?

-
There is one infinite cell, and its boundary consists of every edge. –  Qiaochu Yuan Feb 18 '11 at 21:20
what Qiaochu said –  John Berryman Feb 18 '11 at 21:22