6
$\begingroup$

Except for a few simple cases (typically pyramids and prisms) I find it hard to visualize a polyhedron from its 1-skeleton embedded in the plane, e.g. the hexahedral graph 5, as can be seen here.

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

I am interested in the underlying algorithms and/or heuristics of

  1. drawing the embedded graph from the adjacency matrix

  2. drawing the polyhedron from the adjacency matrix

  3. drawing the polyhedron from the embedded graph

  4. drawing the embedded graph from the polyhedron

I am asking for references.

Computer programs will most certainly deal with (1) and (2) while humans typically have to solve problems (3) and (4).

I guess that experts have some mental techniques to visualize a polyhedron from looking at its 1-skeleton.

Can these techniques be described, made explicit, and taught?

[Side question: If anyone could give me a visualization of the hexahedral graph 5, I would be thankful.]

$\endgroup$
  • 2
    $\begingroup$ Hexahedral graph 5: Take a tetrahedron, glue on one of its faces another tetrahedron and on that one a third tetrahedron, such that the three tetrahedra have one edge in common. Visualisation worked for me because I recognised the graph of the tetrahedron in the heahedral graph. This may be part of a technique. $\endgroup$ – rem Jan 21 '13 at 11:44
  • 1
    $\begingroup$ @Hans: The way you write "the polyhedron" suggests you might be forgetting that these graphs are realized by an infinite variety of combinatorially equivalent polyhedra. $\endgroup$ – Joseph O'Rourke Jan 21 '13 at 13:18
  • $\begingroup$ @Joseph: I was thinking of something like a "prototype". (Of course one can distort a given polyhedron, but basically they are all the same, aren't they?) $\endgroup$ – Hans-Peter Stricker Jan 21 '13 at 13:35
  • $\begingroup$ @Hans: Yes, they are all "the same" in the sense of being combinatorially equivalent. But their visual representations can differ drastically. $\endgroup$ – Joseph O'Rourke Jan 21 '13 at 14:11
8
$\begingroup$

In response to the request for "a visualization of the hexahedral graph 5":
           HexahedraPolyhedron


Just to illustrate the point that there are multiple realizations of any polyhedral graph:
           Wheel5Graph

$\endgroup$
  • 1
    $\begingroup$ It took me a second, but finally I recognized the polyhedron Markus described in his comment (the shared edge fading away in the background). One can describe it another way: take a tetrahedron and make two bends along one edge. $\endgroup$ – Hans-Peter Stricker Jan 21 '13 at 13:39
  • $\begingroup$ @Joseph: Your last example convinced me definitively. Now I see what you mean. Thanks a lot. Should I relax my question and write "an exemplary polyhedron" instead of "the polyhedron"? $\endgroup$ – Hans-Peter Stricker Jan 21 '13 at 17:13
  • $\begingroup$ @Hans: It is an interesting question to find a "natural" realization, perhaps most symmetric. The graph-drawing community has studied this intensively. Just finding some realization is already interesting (and difficult, I think). $\endgroup$ – Joseph O'Rourke Jan 21 '13 at 18:01
  • 1
    $\begingroup$ See also this answer to another question of Hans: mathoverflow.net/questions/120597/… $\endgroup$ – Joseph O'Rourke Feb 3 '13 at 14:54
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

By Steinitz's theorem, your graph will not be the 1-skeleton of a polyhedron unless it is 3-connected.

As indicated on the Wikipedia page, one way to prove Steinitz' theorem is to use circle patterns, which has the advantage that the result circumscribes a sphere (so each edge is tangent to the sphere), uniquely up to projective transformations fixing the sphere.

enter image description here

There are circles for the faces and vertices of the original planar graph (so for the planar graph and its dual). Each circle of the planar graph and its dual is tangent to the adjacent circles of the respective graph. Moreover, the circles associated to a face and a vertex contained in it are orthogonal.

adding circles for the faces

Such circle configurations exist in the plane (and hence on the sphere by stereographic projection) by Andreev's theorem. The point is that the medial graph of the original 3-connected planar graph will be realized as an ideal hyperbolic polyhedron with dihedral angles $\pi/2$. The circles on the 2-sphere will bound hyperbolic planes (the intersection of the plane containing the circle in the Klein ball model of hyperbolic space), so that orthogonal circles correspond to planes meeting orthogonally.

@David Eppstein generated the picture for Wikipedia using the technique described in section 4.2 of this paper.

Incidentally, the identification of the ball with hyperbolic space gives a canonical way to realize a 3-connected graph as a polyhedron up to similarity, by taking the center of the ball to be the hyperbolic center of mass of the polyhedron.

$\endgroup$
4
$\begingroup$

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.

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 Fáry's theorem In fact, such an embedding can also be found with an efficient algorithm [2].

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

(Update) The general case is known as Steinitz's theorem, which states that any 3-connected planar graph is the edge graph of a convex polyhedron. The proof of this theorem isn't trivial, but may give you some insight as to how to turn a planar embedding to a polyhedron. (Note that for 3-connected planar graphs, there's always essentially only one planar embedding, not counting inversions which lets you put infinity into any face, and mirror images.)

As for (4), if you start from a convex 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.

[1] John Hopcroft, Robert Tarjan, "Efficient Planarity Testing", Journal of the Association for Computing Machinery, 21/4 (1974), 549, scanned copy at http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/Planarity%20testing.pdf

[2] Walter Schnyder, "Embedding planar graphs on the grid", SODA '90 Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, (1990), 138-148, scanned copy at http://departamento.us.es/dma1euita/PAIX/Referencias/schnyder.pdf , 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."

$\endgroup$
3
$\begingroup$

Recently, a new visualization technique for polyhedra has been developed, called "boundary interval method". Its detailed exposition is given in the paper

Irene A. Sharaya, Boundary intervals method for visualization of polyhedral solution sets, Reliable Computing, vol. 19, issue 4, pp. 435-467.

Reliable Computing is an open electronic journal, and the direct link to the paper is

http://interval.louisiana.edu/reliable-computing-journal/volume-19/reliable-computing-19-pp-435-467.pdf

Additionally, the paper presents free software that implements the new approach. Maybe, that will help you.

                                      Sergey P. Shary 
                                      http://www.nsc.ru/interval/shary/
$\endgroup$
3
$\begingroup$

The standard answer to this (once you have a planar embedding) is the circle packing theorem This realizes your graph as the one-skeleton of a polyhedron whose edges are tangent to the unit sphere.

$\endgroup$
2
$\begingroup$

As has been noted one can draw diagrams of convex 3-dimensional polyhedra as graphs in the plane. Such diagrams are plane and 3-connected (Steinitz's Theorem) and are essentially unique but can be very different in visual appearance because one has the freedom to choose the infinite face. So if the polyhedron has a k-gon face one can draw a plane representation (with straight line edges and convex regions except for the infinite face) with a k-gon as the infinite face.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.