TR-2019-10

Compressed frameworks and compressible graphs

Tibor Jordán, Jialin Zhang



Abstract

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}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!