# Abstract characterization of polygonizations

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

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.

-
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

## 2 Answers

Voronoi digram/tessellation. http://en.wikipedia.org/wiki/Voronoi_diagram

-
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

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.

-
@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