Abstract characterization of polygonizations - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T05:16:56Z http://mathoverflow.net/feeds/question/114911 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114911/abstract-characterization-of-polygonizations Abstract characterization of polygonizations Hans Stricker 2012-11-29T18:44:42Z 2012-11-30T08:57:39Z <p>Consider a <a href="http://en.wikipedia.org/wiki/Triangulation_%2528geometry%2529" rel="nofollow">polygonization</a> of the plane by convex polygons of a given minimal size that meet edge-to-edge and vertex-to-vertex.</p> <p><img src="http://i.stack.imgur.com/cYI09.png" alt="enter image description here"> <em><sup>What's the &ldquo;official&rdquo; name of such a polygonization?</sup></em></p> <p>Such polygonizations of the plane induce infinite graphs.</p> <blockquote> <p>How can such abstract graphs be characterized?</p> </blockquote> <p>Somehow like this: &ldquo;A graph is induced by a polygonization of the plane iff it is infinite, planar, 3-vertex-connected, and <em>P</em>.&rdquo; (The question asks for property <em>P</em>, since infinite, planar and 3-vertex-connected those graphs obviously are.)</p> <blockquote> <p>Is it true, that the graphs that are induced by a polygonization of the <em>sphere</em> are exactly the <a href="http://en.wikipedia.org/wiki/Polyhedral_graph" rel="nofollow">polyhedral graphs</a> which in turn are exactly the finite planar <a href="http://en.wikipedia.org/wiki/Steinitz%27s_theorem" rel="nofollow">3-vertex-connected graphs</a>?</p> </blockquote> <p>Finally I want to know:</p> <blockquote> <p>Can the graphs be characterized that are induced by a polygonization of <em>any</em> surface?</p> </blockquote> <p><sup>For the record: I asked this question at <a href="http://math.stackexchange.com/questions/246929/graphs-that-polygonize-a-manifold" rel="nofollow">MSE</a> before but it didn't earn a lot of interest.</sup></p> http://mathoverflow.net/questions/114911/abstract-characterization-of-polygonizations/114935#114935 Answer by Chad Brewbaker for Abstract characterization of polygonizations Chad Brewbaker 2012-11-29T22:13:28Z 2012-11-29T22:13:28Z <p>Voronoi digram/tessellation. <a href="http://en.wikipedia.org/wiki/Voronoi_diagram" rel="nofollow">http://en.wikipedia.org/wiki/Voronoi_diagram</a> </p> http://mathoverflow.net/questions/114911/abstract-characterization-of-polygonizations/114947#114947 Answer by Igor Rivin for Abstract characterization of polygonizations Igor Rivin 2012-11-30T01:16:01Z 2012-11-30T01:16:01Z <p>For the OP's claim re *infinite*polyhedral graphs, the answer is yes, this is true, and a proof is in my paper:</p> <p>Rivin, Igor. "Combinatorial optimization in geometry." Advances in Applied Mathematics 31.1 (2003): 242-271.</p> <p>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 <em>any</em> Jordan domain.</p>