14
$\begingroup$

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.

  • 0
    Intuitively it seems that such "cell" construction would have bounded doubling dimensions, whereas planar graphs can have unbounded doubling dimension2011-02-18

4 Answers 4

11

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.

  • 0
    Tangent: One of the proofs of Sylvester-Gallai theorem uses this planar graph representation.2011-02-18
2

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.

  • 0
    perhaps, but when we start talking about geodesics, we're getting away from the more pure topological questions I was interested in.2011-02-22
1

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


(source: yaroslavvb.com)

  • 0
    what Qiaochu said2011-02-18
0

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