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