Stable Planar Graphs Under Hooke's Law

72 Views Asked by At

Given a planar graph, i. e. a graph $G=(V,E)$ with a map $p\colon V\to\mathbf{R}^2$ (could also be $\mathbf{R}^n$), we can imagine the edges being springs following Hooke's law. I write $\text{len}_p(e)$ for the length of $e:=\{v,v'\}$ under $p$, i. e. $\|p(v')-p(v)\|$. So for another planar map $p'\colon V\to\mathbf{R}^2$ we can compute the force on some vertex $v\in V$ as $$\sum_{v'\in V\colon (e:=\{v,v'\})\in E}(\text{len}_{p'}(e)-\text{len}_p(e))(p'(v')-p'(v))/\text{len}_{p'}(e)$$ (if I'm not mistaken). I did some simulations and realized that (obviously) for some planar graphs $(G,p)$, there are alternative planar maps $p'$ which are not congruent to $p'$ but still stable, i. e. all forces sum up to $0$. (Some of them are trivial in the sense that all springs retain their rest length, but there are non-trivial ones as well.) I was just curious if this has been studied in graph theory, or alternatively the question, given $k$ points in $\mathbf{R}^2$, what is the least amount of springs needed to turn the configuration into a stable graph as defined above?