Visualizing polyhedra from their 1-skeletons - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T02:16:53Z http://mathoverflow.net/feeds/question/119455 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119455/visualizing-polyhedra-from-their-1-skeletons Visualizing polyhedra from their 1-skeletons Hans Stricker 2013-01-21T10:58:43Z 2013-03-28T10:17:42Z <p>Except for a few simple cases (typically pyramids and prisms) I find it hard to visualize a polyhedron from its 1-skeleton <a href="http://en.wikipedia.org/wiki/Graph_embedding" rel="nofollow">embedded</a> in the plane, e.g. the hexahedral graph 5, as can be seen <a href="http://mathworld.wolfram.com/PolyhedralGraph.html" rel="nofollow">here</a>.</p> <p>Tools that are able to take an arbitrary polyhedral graph as input and draw the corresponding polyhedron perspectively will most surely rely on an abstract representation of the graph, e.g. by its adjacency matrix. From this abstract representation - presumably - they will also draw the embedded version of the graph (without edges crossing).</p> <p>I am interested in the underlying algorithms and/or heuristics of</p> <blockquote> <ol> <li><p>drawing the embedded graph from the adjacency matrix</p></li> <li><p>drawing the polyhedron from the adjacency matrix</p></li> <li><p>drawing the polyhedron from the embedded graph </p></li> <li><p>drawing the embedded graph from the polyhedron</p></li> </ol> </blockquote> <p>I am asking for references.</p> <p>Computer programs will most certainly deal with (1) and (2) while humans typically have to solve problems (3) and (4). </p> <p>I guess that experts have some mental techniques to visualize a polyhedron from looking at its 1-skeleton.</p> <blockquote> <p>Can these techniques be described, made explicit, and taught?</p> </blockquote> <p><em>[Side question: If anyone could give me a visualization of the hexahedral graph 5, I would be thankful.]</em></p> http://mathoverflow.net/questions/119455/visualizing-polyhedra-from-their-1-skeletons/119466#119466 Answer by Joseph O'Rourke for Visualizing polyhedra from their 1-skeletons Joseph O'Rourke 2013-01-21T13:16:50Z 2013-03-26T23:54:36Z <p>In response to the request for "a visualization of the hexahedral graph 5": <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/HexahedralGraph.jpg" alt="HexahedraPolyhedron" /> <br /></p> <p><hr /> Just to illustrate the point that there are multiple realizations of any polyhedral graph: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/Wheel5ab.jpg" alt="Wheel5Graph" /> <br /></p> http://mathoverflow.net/questions/119455/visualizing-polyhedra-from-their-1-skeletons/125649#125649 Answer by Vince Matsko for Visualizing polyhedra from their 1-skeletons Vince Matsko 2013-03-26T18:31:57Z 2013-03-26T18:31:57Z <p>It should be noted that the adjacency matrix does not uniquely determine the polyhedron. In fact, the small stellated dodecahedron and the great icosahedron have the same adjacency matrix, but are not combinatorially equivalent.</p> http://mathoverflow.net/questions/119455/visualizing-polyhedra-from-their-1-skeletons/125810#125810 Answer by Zsbán Ambrus for Visualizing polyhedra from their 1-skeletons Zsbán Ambrus 2013-03-28T10:11:53Z 2013-03-28T10:17:42Z <p>For your question (1), there is an efficient algorithm [1] known for finding an embedding of a graph in the plane if an embedding exists. </p> <p>This, however, might not be the end of the story. You may want to get an embedding where every edge is a straight line segment. It is known that such an embedding always exists if there is an embedding and there are no duplicate edges, this is called <a href="http://en.wikipedia.org/wiki/F%C3%A1ry%27s_theorem" rel="nofollow">Fáry's theorem</a> In fact, such an embedding can also be found with an efficient algorithm [2].</p> <p>Your question (3) is turning a planar embedding to a polyhedron embedded in the space. This has an easy special case: namely if all faces of the planar embedding are <em>triangles</em> and all edges are straight segments. In this case, you can get a polyhedron embedding by slightly bending the plane so you get a sphere with a large radius, then fixing the vertexes and straightening the edges and faces. I believe but I'm not sure that this can be extended to the case when there is one or two faces that are not triangular, but there might not be such an easy method in the general case.</p> <p>As for (4), if you start from a <em>convex</em> polyhedron, you can get a planar embedding, not necessarily with straight edges, by first projecting the vertexes and edges of the polyhedron to a sphere inside the polyhedron, then projecting that sphere to the plane.</p> <p>[1] John Hopcroft, Robert Tarjan, "Efficient Planarity Testing", <em>Journal of the Association for Computing Machinery</em>, <strong>21</strong>/4 (1974), 549, scanned copy at <a href="http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/Planarity%20testing.pdf" rel="nofollow">http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/Planarity%20testing.pdf</a></p> <p>[2] Walter Schnyder, "Embedding planar graphs on the grid", <em>SODA '90 Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms</em>, (1990), 138-148, scanned copy at <a href="http://departamento.us.es/dma1euita/PAIX/Referencias/schnyder.pdf" rel="nofollow">http://departamento.us.es/dma1euita/PAIX/Referencias/schnyder.pdf</a> , ISBN:0-89871-251-3. Abstract: "We show that each plane graph of order n ≥ 3 has a straight line embedding on the n − 2 by n − 2 brid. This embedding is computable in time O(n). A nice feature of the vertex-coordinates is that they have a purely combinatorial meaning."</p>