Characterizing globally linked pairs in graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915892621737984 |
|---|---|
| author | Jordán, Tibor Tanigawa, Shin-ichi |
| author_facet | Jordán, Tibor Tanigawa, Shin-ichi |
| contents | A pair $\{u,v\}$ of vertices is said to be globally linked in
a $d$-dimensional framework $(G,p)$ if there exists no other
framework $(G,q)$ with the same edge lengths, in which the
distance between the points corresponding to $u$ and $v$
is different from that in $(G,p)$.
We say that $\{u,v\}$ is globally linked in $G$ in $\R^d$ if
$\{u,v\}$ is globally linked in every generic $d$-dimensional framework $(G,p)$.
We give a complete combinatorial characterization of globally linked
vertex pairs in graphs in $\R^2$, solving a
conjecture of Jackson, Jordán and Szabadka from 2006 in the affirmative.
Our result provides a refinement of the characterization of globally rigid graphs in $\R^2$ as well as an efficient algorithm for finding the globally linked pairs in a graph. We can also deduce that globally linked pairs in $\R^2$, globally linked pairs in ${\mathbb C}^2$, and stress-linked pairs in ${\mathbb R}^2$ are all the same,
settling conjectures of Jackson and Owen, and Garamvölgyi, respectively.
In higher dimensions we determine the
globally linked pairs in body-bar graphs in $\R^d$, for all $d\geq 1$, verifying
a conjecture of Connelly, Jordán and Whiteley. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_25428 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Characterizing globally linked pairs in graphs Jordán, Tibor Tanigawa, Shin-ichi Combinatorics 52C25 A pair $\{u,v\}$ of vertices is said to be globally linked in a $d$-dimensional framework $(G,p)$ if there exists no other framework $(G,q)$ with the same edge lengths, in which the distance between the points corresponding to $u$ and $v$ is different from that in $(G,p)$. We say that $\{u,v\}$ is globally linked in $G$ in $\R^d$ if $\{u,v\}$ is globally linked in every generic $d$-dimensional framework $(G,p)$. We give a complete combinatorial characterization of globally linked vertex pairs in graphs in $\R^2$, solving a conjecture of Jackson, Jordán and Szabadka from 2006 in the affirmative. Our result provides a refinement of the characterization of globally rigid graphs in $\R^2$ as well as an efficient algorithm for finding the globally linked pairs in a graph. We can also deduce that globally linked pairs in $\R^2$, globally linked pairs in ${\mathbb C}^2$, and stress-linked pairs in ${\mathbb R}^2$ are all the same, settling conjectures of Jackson and Owen, and Garamvölgyi, respectively. In higher dimensions we determine the globally linked pairs in body-bar graphs in $\R^d$, for all $d\geq 1$, verifying a conjecture of Connelly, Jordán and Whiteley. |
| title | Characterizing globally linked pairs in graphs |
| topic | Combinatorics 52C25 |
| url | https://arxiv.org/abs/2603.25428 |