Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a graph $G=(V,E)$ and a length function $\ell:E\to\mathbb{R}_+$. An embedding of the graph into the $d$-dimensional Euclidean space is a map $f:V\to\mathbb{R}^d$ such that $||f(u)-f(v)||=\ell(uv)$ if $uv\in E$. (So $(G,f)$ is actually a framework in terms of rigidity theory.)

I'm thinking about finding an embedding that maximize the volume of the convex hull of the point set $\{f(v)\mid v\in V\}$ in $\mathbb{R}^d$ (the dimension in question is fixed).

Of course, we should assume the existence of an embedding, and that the framework is not globally rigid, otherwise the answer is trivial.


let $G$ be a $m\times n$ grid graph, $\ell=1$ and $d=2$. Then the embedding maximizing the volume is the canonical one: part of the square lattice.

share|cite|improve this question
any one tell me how to type the braket {} for a set? \{ \} doesn't work. – Hao Chen Mar 18 '13 at 13:56
Use double backslashes \\{ \\} – Bati Mar 18 '13 at 15:11
A volume maximizing embedding always exists because the space of embeddings is compact. – David Cohen Mar 18 '13 at 16:09
@David Cohen: Yes of course. But we need to assume that an embedding exists at the first place. I mean, situation like $G=C_3$ (triangle), $\ell=3,4,10$ should not be considered. – Hao Chen Mar 18 '13 at 17:45
I believe I can see how to show that minimizing the volume is NP-hard, and I suspect that maximizing is equally difficult. – Joseph O'Rourke Mar 19 '13 at 1:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.