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

• What do you mean by a 'cap' and its 'boundary'? Commented Sep 21, 2017 at 12:40
• We can think of the cap as the graph of a piecewise linear concave function over P with zero boundary values. So it looks like a dome over P. Further the cap is a topological disk, so its boundary is just the topological boundary of the disk. Commented Sep 21, 2017 at 15:15
• Consider a convex quadrilateral partitioned by a diagonal. What is a function? Commented Sep 21, 2017 at 15:37
• In that case the function would be zero and the cap would be degenerate. The question is interesting only when the partition has some vertices in the interior of the polygon. Commented Sep 21, 2017 at 15:44
• But for degenerated cup there is no difference between two diagonals. If it counts in this situation, why it does not count for inner vertices too? Commented Sep 21, 2017 at 16:13

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.

• Thank you! I will look up the references. In the meantime I wonder: are there necessary an sufficient conditions known for the existence of a lifting of the subdivision to a convex cap? If so, are there explicit procedures for constructing the cap? Commented Sep 21, 2017 at 15:07
• Dear Mohammad, I've edited my answer to adress this question as well. Commented Sep 21, 2017 at 15:50
• Ivan Izmestiev is being modest; he has written a nice survey that covers the Maxwell-Cremona correspondence arxiv.org/abs/1707.02172
– j.c.
Commented Sep 21, 2017 at 17:28

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.

• This sounds like it would be more restrictive than the situation I am asking about, as it corresponds to the case where each face of the subdivision has an edge on the boundary of the polygon P. But it still would be nice to know how things would work out in this case. So you say that this follows from the Proof of Steinitz theorem? Commented Sep 22, 2017 at 0:18
• Graphs of the kind that I describe are sometimes called Halin graphs, and they have many nice properties: See, Bondy, J.A. and Lovász, L., 1985. Lengths of cycles in Halin graphs. Journal of graph theory, 9(3), pp.397-410. The extension of Steinitz Theorem I refer to can be found in the paper here: msp.org/pjm/1970/32-2/pjm-v32-n2-p02-s.pdf Commented Sep 22, 2017 at 16:23