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.

  • $\begingroup$ Intuitively it seems that such "cell" construction would have bounded doubling dimensions, whereas planar graphs can have unbounded doubling dimension $\endgroup$ – 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.

  • $\begingroup$ 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 $\endgroup$ – Yaroslav Bulatov Feb 18 '11 at 21:32
  • $\begingroup$ @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. $\endgroup$ – Qiaochu Yuan Feb 18 '11 at 21:45
  • 2
    $\begingroup$ I think Qiaochu means tesselating. $\endgroup$ – John Berryman Feb 18 '11 at 21:46
  • $\begingroup$ ... although that might still not be precise here... $\endgroup$ – John Berryman Feb 18 '11 at 21:47
  • $\begingroup$ Tangent: One of the proofs of Sylvester-Gallai theorem uses this planar graph representation. $\endgroup$ – 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.

  • $\begingroup$ That's kind a interesting. $\endgroup$ – John Berryman Feb 20 '11 at 4:04
  • $\begingroup$ @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. $\endgroup$ – lhf Feb 22 '11 at 11:09
  • $\begingroup$ perhaps, but when we start talking about geodesics, we're getting away from the more pure topological questions I was interested in. $\endgroup$ – John Berryman Feb 22 '11 at 14:21

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

(source: yaroslavvb.com)

  • 1
    $\begingroup$ There is one infinite cell, and its boundary consists of every edge. $\endgroup$ – Qiaochu Yuan Feb 18 '11 at 21:20
  • $\begingroup$ what Qiaochu said $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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