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 points $f(v)$, $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.

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.

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 points $f(v)$, $v\in V$ in $\mathbb{R}^d$ (the dimension in question is fixed).

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 points $f(v)$, $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.