Convex caps with prescribed edges Let $P$ be a convex polygon in the plane $R^2=R^2\times \{0\}$, and $E$ be the edge graph of some subdivision of $P$ into convex polygons, which is $3$-connected. Does there exist a convex polyhedral cap $C\subset R^3$ such that the boundary of $C$ coincides with that of $P$, and the orthogonal projection of the edges of $C$ into $R^2$ coincide with $E$?
A convex polyhedral cap is a portion of the surface of a convex polyhedron cut off by a plane which contains an interior point of the polyhedron.  
Addendum : The answer to this question is also discussed in a reply by Andy B. to an earlier question.
 A: No. A subdivision that can be lifted to a convex cap is called regular (or coherent, or weighted Delaunay). Here is an example of a non-regular subdivision:

For more on this, I recommend the book "Triangulations" by De Loera, Santos, Rambau.
A subdivision can be lifted to a (non-necessarily convex) polyhedron if and only if it admits an equilibrium stress. This is an assignment of real numbers to the edges such that the sum of the forces acting at every vertex is zero. Convex polyhedral lifts correspond to stresses that are positive on the interior edges and negative on the boundary edges. The keywords here are the Maxwell-Cremona correspondence.
To find a stress, one has to solve a system of linear equations. To determine whether there is a positive stress, one has to check whether the solution space intersects the interior of a polyhedral cone.
A: I am not exactly sure what your "rules" are here. If one starts with a tree embedded in the plane whose vertices which are not 1-valent (degree 1) all have valence at least 3 and one passes a simple closed curve C through the 1-valent vertices of the tree, then the resulting graph is plane and 3-connected. This graph can be used to construct a 3-polytope (using a strengthening of Steinitz's Theorem) where the face corresponding to C is a regular polygon, and the vertices and edges of the original tree lie above C.
