How to go from a skeleton of a polyhedron to a pretty good drawing? Suppose you have a graph which represents the skeleton (vertices and edges) of a polyhedron.
I know I can easily construct a planar embedding Tutte embedding, but how do you convert this to a figure in 3 dimensions?
 A: If you want to restore the polygon, the important step is to find the cells of the planar graph (faces of the polygon).
One of the possible ways to do this is:


*

*Enumerate vertices ($i$) and edges ($\alpha$). Let the total number of edges be $M$. For each edge $\alpha$ adjacent to vertices $i,j$, define $f_\alpha(i)=j$

*For each vertex $i$, take a list of adjacent edges, sort it by angle.

*For each pair of consequent edges $\alpha$, $\beta$ in that circular list, create a pair $(Y_\alpha^i, Y_\beta^{f_\beta(i)})$, where
$$
Y_\alpha^i = \begin{cases}\alpha& i>f_\alpha(i)\\\alpha+M & i<f_\alpha(i)\end{cases}
$$

*Set of all pairs $(Y_n, Y_m)$ will give you graph containing several disconnected circular components, each of which is a face.


Short explanation. Each edge belongs to exactly two faces and is traversed in opposite direction, when we traverse faces clockwise. Thus, we split each edge $\alpha$ into edge 
$\alpha$ and $\alpha+M$ and connect edges on one face.
Then you take the initial solution as a stereographic projection and try to flatten all the faces as an optimization problem. On each optimization step, you can fit a plane to each set of vertices that belong to one face (for example by SVD), and calculate functional:
$$
J=\sum_{\text{all faces}} \sum_{\text{all face vertices}}(\text{distance to fit plane})^2
$$
and take a gradient descent step that decrease $J$. After each optimization step, you might want to renormalize your points (set center of mass to origin and normalize by mean distance to origin, for example).
You might want to also introduce some other constraints to the functional to even the edges or angles of the faces, but don't forget to relax them, when you will get closer to flat faces.
