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.

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.

share|improve this question
    
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

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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?

share|improve this answer
1  
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

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.