TR-2004-02

Rigid two-dimensional frameworks with three collinear points

Bill Jackson, Tibor Jordán

Published in:
Graphs and Combinatorics, December 2005, Volume 21, Issue 4, pp 427-444



Abstract

Let G=(V,E) be a graph and x,y,z \in V be three designated vertices. We give a necessary and sufficient condition for the existence of a rigid two-dimensional framework (G,p), in which x,y,z are collinear. This result extends a classical result of Laman on the existence of a rigid framework on G. Our proof leads to an efficient algorithm which can test whether G satisfies the condition.


Bibtex entry:

@techreport{egres-04-02,
AUTHOR = {Jackson, Bill and Jord{\'a}n, Tibor},
TITLE = {Rigid two-dimensional frameworks with three collinear points},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2004},
NUMBER = {TR-2004-02}
}


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