5
$\begingroup$

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.

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

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @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)? $\endgroup$
    – Hans-Peter Stricker
    Commented Nov 30, 2012 at 8:55
  • $\begingroup$ @Hans: that's one way of thinking of it. As for the paper, you can get it on arxiv in some version... $\endgroup$
    – Igor Rivin
    Commented Dec 1, 2012 at 4:43
-2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ Are you claiming that Voronoi diagrams, which are a very special sort of polygonization, are relevant to this question? $\endgroup$
    – Andreas Blass
    Commented Nov 29, 2012 at 23:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .