Abstract characterization of polygonizations - MathOverflow

Abstract characterization of polygonizations

2012-11-29T18:44:42Z

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

Answer by Chad Brewbaker for Abstract characterization of polygonizations

2012-11-29T22:13:28Z

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

Answer by Igor Rivin for Abstract characterization of polygonizations

2012-11-30T01:16:01Z

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.