# Graph drawing maximizing the volume of the convex hull

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.

Example

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.

-
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