Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What's the "official" name of a connected planar graph consisting entirely of polygons (cycles), glued together at edges, e.g. - among other things - without "end vertices" (of degree 1) and without edges not belonging to an inner face. Maybe something like "planar foam graph"?

Has this concept been generalized to higher dimensions: "3D foam graphs" (entirely consisting of polyhedrons, glued together at faces) and so on?

share|cite|improve this question
I mean the outer face that you mean: the one that always exists when you draw a (finite) planar graph in the plane. And I wanted to exclude planar graphs like "two triangles connected by an edge" - the latter (edge) would not belong to an inner face. – Hans Stricker Aug 23 '12 at 17:35
up vote 2 down vote accepted

It took me a while to figure out what you mean. To clarify a few things first. A planar graph does not come with faces. It depends on the combinatorial embedding of the graph, which determines the faces. However, if the graph is 3-vertex-connected, the combinatorial embedding is unique (up to a global reflection). Moreover, even if you have fixed the combinatorial embedding, you can draw every face as the outer face.

The graphs you are asking for have the following property. When deleting one edge, the graph will not split into two unconnected subgraphs. This property is known as 2-edge-connected. So you are interested in the planar 2-edge-connected graphs. The "3d generalization" could be the planar 3-edge-connected graphs, but I am not sure what you mean by this.

share|cite|improve this answer
Thank you very much for having tried to figure out! And you guessed right: I obviously had 2-edge-connected planar graphs in mind! I have to think about 3D generalization, but I would guess that this should mean: "deleting one 'face' the graph will not split into two unconnected subgraphs, i.e. 2-face-connected? – Hans Stricker Aug 23 '12 at 19:28
Let me understand correctly: Even in 3-vertex-connected planar graphs I can draw every face as the outer face? (This would make my formulation of the question pointless.) – Hans Stricker Aug 23 '12 at 19:29
@HansStricker: You are right. By Steinitz Theorem every planar 3-connected graph can be realized as convex 3d polytope. Take any face $f$ and project all other vertices on $f$ (centrally to a vertex just behind $f$). In this way you get a Schlegel diagramm, which is a crossing free drawing of the graph, with $f$ as outer face, and all faces drawn as convex polygons. – A.Schulz Aug 23 '12 at 19:58

Your Answer


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.