|
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:
| AUTHOR | = | {Jord{\'a}n, Tibor and Zhang, Jialin}, |
| TITLE | = | {Compressed frameworks and compressible graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2019}, |
| NUMBER | = | {TR-2019-10} |