A $d$-dimensional framework is a pair $(G,p)$, where $G=(V,E)$
is a graph and $p$ maps the vertices of $G$ to points in
$\mathbb{R}^d$. The edges correspond to the line segments that connect the
points of their end-vertices.
We say that $(G,p)$ is {compressed} if in every other
framework $(G,q)$, with the same graph $G$ and with the same edge-lengths,
we have $||p(u)-p(v)||\leq ||q(u)-q(v)||$ for all pairs $u,v\in V$, where
$||.||$ denotes the Euclidean norm in $\mathbb{R}^d$.
A graph $G$ is said to be compressible in $\mathbb{R}^d$
if there exists a compressed $d$-dimensional framework $(G,p)$.
We characterize the compressible graphs in $\mathbb{R}^1$ and give some partial results
in the two-dimensional case. We also consider the case when the
coordinates of the points are generic.
Bibtex entry:
@techreport{egres-19-10,
AUTHOR | = | {Jord{\'a}n, Tibor and Zhang, Jialin}, |
TITLE | = | {Compressed frameworks and compressible graphs}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2019}, |
NUMBER | = | {TR-2019-10} |