MathOverflow is a question and answer site for professional mathematicians. 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

Consider a polygonization of the plane by convex polygons of a given minimal size that meet edge-to-edge and vertex-to-vertex.

enter image description here What's the “official” name of such a polygonization?

Such polygonizations of the plane induce infinite graphs.

How can such abstract graphs be characterized?

Somehow like this: “A graph is induced by a polygonization of the plane iff it is infinite, planar, 3-vertex-connected, and P.” (The question asks for property P, since infinite, planar and 3-vertex-connected those graphs obviously are.)

Is it true, that the graphs that are induced by a polygonization of the sphere are exactly the polyhedral graphs which in turn are exactly the finite planar 3-vertex-connected graphs?

Finally I want to know:

Can the graphs be characterized that are induced by a polygonization of any surface?

For the record: I asked this question at MSE before but it didn't earn a lot of interest.

share|cite|improve this question
Do you know the infinite version of Steinitz' theorem? – Igor Rivin Nov 29 '12 at 18:48
No, I don't, can you give me a reference, please? – Hans Stricker Nov 29 '12 at 18:49
I asked because you claimed that the polyhedral graphs are the 3-vertex connected graphs... – Igor Rivin Nov 30 '12 at 1:12
What do you mean by minimal size? Combinatorially minimal or metrically minimal? – Brian Rushton Nov 30 '12 at 4:09
Sorry for not having been specific: I meant metrically minimal (to avoid some "fractal" kind of polygonization). – Hans Stricker Nov 30 '12 at 8:42

For the OP's claim re *infinite*polyhedral graphs, the answer is yes, this is true, and a proof is in my paper:

Rivin, Igor. "Combinatorial optimization in geometry." Advances in Applied Mathematics 31.1 (2003): 242-271.

Basically, you can construct a circle packing with any prescribed (three-connected) combinatorics. What you lose when you go from finite to infinite is uniqueness, in a spectacular way: it should be true that one can get the carrier of the packing to be any Jordan domain.

share|cite|improve this answer
@Igor, thank you very much, I'll try to get your paper. For my better understanding: Is it correct, that the infinite planar 3-vertex-connected graphs are induced by polygonizations of the plane as specified above (edge-to-edge, vertex-to-vertex) and the finite planar 3-vertex-connected graphs are induced by polygonizations of the sphere (a.k.a. polyhedra)? – Hans Stricker Nov 30 '12 at 8:55
@Hans: that's one way of thinking of it. As for the paper, you can get it on arxiv in some version... – Igor Rivin Dec 1 '12 at 4:43

Voronoi digram/tessellation.

share|cite|improve this answer
Are you claiming that Voronoi diagrams, which are a very special sort of polygonization, are relevant to this question? – Andreas Blass Nov 29 '12 at 23:55

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.