TR-2010-02

Globally linked pairs of vertices in minimally rigid graphs

Zoltán Szabadka



Abstract

A 2-dimensional framework (G,p) is a graph G=(V,E) together with a map p: V \to R2. We view (G,p) as a straight line realization of G in R2. We shall only consider generic frameworks, in which the co-ordinates of all the vertices of G are algebraically independent. Two realizations of G are equivalent if the corresponding edges in the two frameworks have the same length. A pair of vertices {u,v} is globally linked in G if the distance between the points corresponding to u and v is the same in all pairs of equivalent generic realizations of G. We extend the characterization of globally linked pairs of vertices given by Jackson, Jordán and the author by characterizing globally linked pairs in minimally rigid graphs. In minimally rigid graphs, only those pairs of vertices are globally linked that are connected by an edge.


Bibtex entry:

@techreport{egres-10-02,
AUTHOR = {Szabadka, Zolt{\'a}n},
TITLE = {Globally linked pairs of vertices in minimally rigid graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2010},
NUMBER = {TR-2010-02}
}


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