User:MWinter4/Maxwell-Cremona correspondence

The Maxwell-Cremona correspondence is a result in the intersection of graph theory, rigidity theory and polytope theory. It establishes a one-to-one correspondence between the equilibrium stresses, reciprocal diagrams and polyhedral liftings of a planar straight-line drawing of a 3-connected graph. Its most important consequence is that the planar drawing has a non-zero stress if and only if it has a non-trivial polyhedral lifting.

Relevant terminology

Let $G=(V,E)$ be a 3-connected planar graph. A planar straight-line drawing of $G$ is a map ${\boldsymbol {p}}:V\to {\mathbb {R}}^{2}$ that to each vertex $v\in V$ assigns a point $p_{v}\in {\mathbb {R}}^{2}$ in the plane, so that no two edges, drawn as straight lines between these points, intersect anywhere but their ends. The drawing divides the plane into polygonal regions. By $F$ we denote the set of these regions, or faces, of the drawing.

Equilibrium stresses

A stress for the drawing assigns to each edge $e\in E$ a real number $\omega _{e}\in {\mathbb {R}}$. The stress is said to be an equilibrium stress if

$\sum _{w\,:\,vw\in E}\!\!\!\!\omega _{vw}(p_{v}-p_{w})=0\quad$ for all vertices $v\in V$.

This has the following physical interpretation: each edge $e=vw\in E$ is considered as a spring with (potentially zero or negative) spring constant $\omega _{e}$ and equilibrium length zero. By Hook's law the spring pulls on its ends with force $\pm \omega _{vw}(p_{v}-p_{w})$. In an equilibrium stress these forces cancel at each vertex.

Reciprocal diagrams

The dual graph $G^{*}=(V^{*},E^{*})$ has as vertex set $V^{*}:=F$ the regions of the drawing, two of which are adjacent if they bound a common edge. Each edge $vw\in E$ is incident to exactly two regions in the drawing, say $f,g\in F$, and hence corresponds to an edge $fg\in E^{*}$, and vice versa.

A straight-line drawing ${\boldsymbol {q}}:F\to {\mathbb {R}}^{2}$ of $G^{*}$ is called a reciprocal drawing or reciprocal diagram to ${\boldsymbol {p}}$ if corresponding edges $vw\in E$ and $fg\in E^{*}$ are drawn as lines that are perpendicular to each other. Formally,

$(q_{f}-q_{g})^{\top }(p_{v}-p_{w})=0.$

Polyhedral liftings

A lifting of ${\boldsymbol {p}}$ is a map ${\boldsymbol {h}}:V\to {\mathbb {R}}$ that to each vertex $v\in V$ assigns a height $h_{v}$. This yields a lifted drawing ${\bar {\boldsymbol {p}}}:V\to {\mathbb {R}}^{3}$ in 3-dimensional Euclidean space with ${\bar {p}}_{v}:=(p_{v},h_{v})$.

The lifting is a polyhedral lifting if the vertices that bound a common region in the darwing ${\boldsymbol {p}}$ are lifted to lie on a common plane in ${\mathbb {R}}^{3}$.

Formal statement

Let ${\boldsymbol {p}}$ be a planar straight-line drawing of a 3-connected planar graph $G=(V,E)$. Let $F$ be the set of regions in the drawing. Then there exists a one-to-one correspondences between the equilibrium stresses, reciprocal diagrams and polyhedral liftings of ${\boldsymbol {p}}$.

In particular, the following are equivalent:

• ${\boldsymbol {p}}$ has a non-zero equilibrium stress ${\boldsymbol {\omega }}:E\to {\mathbb {R}}$.
• ${\boldsymbol {p}}$ has a non-trivial reciprocal diagram ${\boldsymbol {q}}:F\to {\mathbb {R}}^{2}$.
• ${\boldsymbol {p}}$ has a non-trivial polyhedral lifting ${\boldsymbol {h}}:V\to {\mathbb {R}}$.

The sign of the stress at an interior edge $e\in E$ determines whether the lifiting will be convex or concave at this edge: the stress at $e$ is positive/zero/negative if and only if the corresponding lifiting is convex/flat/concave at $e$. In particular, there exists a convex lifiting if and only if there exists a stress that is positive at all interior edges.

One-to-one correspondence

Let $(G,{\boldsymbol {p}})$ be a planar straight-line drawing of $G$. Let $ij\in E(G)$ be an edge and $uv\in E(G^{*})$ be the corresponding dual edge, appropriately oriented. It is a key ingredient to this proof that there is a way to choose globally compatible orientations of $G$ and $G^{*}$.

We will use the following notation:

• $(G,{\boldsymbol {q}})$ is the reciprocal diagram.
• ${\boldsymbol {\omega }}$ is the stress.
• $h:V\to {\mathbb {R}}$ is a lifting function, which to each vertex assignes a hight.

From a stress to a reciprocal diagram

Edges of the reciprocal diagram $(G^{*},{\boldsymbol {q}})$ are perpendicular to edges in $(G,{\boldsymbol {p}})$. This is expressed by the following equation, in which $R_{\pi /2}$ is the 90°-rotation matrix:

$q_{u}-q_{v}=\omega _{ij}R_{\pi /2}(p_{i}-p_{j}).$

That this equation can be solved for ${\boldsymbol {q}}$ follows from the definition of the stress and the choice of a compatible orientation.

From a reciprocal diagram to a stress

$\omega _{ij}:={\frac {\|p_{i}-p_{j}\|}{\|q_{u}-q_{v}\|}}.$

From a polyhedral lifting to a reciprocal diagram

Let $q_{u}$ be the gradient of the face $u$.

From a reciprocal diagram to a polyhedral lifting

Solve

$h_{i}-h_{j}=q_{u}^{\top }(p_{i}-p_{j}).$

Relations and Applications

Tutte embeddings and Steinitz's theorem

Given any 3-connected planar graph $G$ and a non-separating induced cycle $C$ in $G$, the Tutte embedding yields a planar drawing of this graph in which $C$ is the outer face and where there exists a stress that is in equilibrium on every inner vertex. If the outer face is a triangle, then this stress can be extended to all edges.

This fact can be used to prove Steinitz's theorem if $G$ conatins a triangle. If it does not contain a triangle, then it contains a vertex of degree three, and one can instead construct a Tutte embedding of the dual graph. Lifting this embedding yields a realization of the dual polytope.

Weighted Delaunay triangulations

...

Generalizations