# 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

Another -- I think more natural -- concept is the (PL)-embeddability of $k$-dimensional simplicial complexes into $R^d$, for certain pairs $k,d$. The case $k=1$, $d=2$ is graph planarity.

There are many recent algorithmic result on this, including polynmiality in the metastable dimension range ($d\geq 3(k+1)/2$) with fixed dimensions, NP-hardness (and probably undecidability) for larger $k$, and proven undecidability for $k=d$.