Welcome to MathOverflow

Question

5

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

edited Nov 30 at 8:57

asked Nov 29 at 18:44

Hans Stricker
5,233●12●38

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

Igor Rivin · Answer 1 · 2012-11-30 01:16:01Z UTC

2

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.

answered Nov 30 at 1:16

Igor Rivin
31.1k●3●37●71

	@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 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 at 4:43

Chad Brewbaker · Answer 2 · 2012-11-29 22:13:28Z UTC

-1

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

answered Nov 29 at 22:13

Chad Brewbaker
11●2

3

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

Abstract characterization of polygonizations

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.