Rigid Two-Dimensional Frameworks with Three Collinear Points

Let G = (V, E) be a graph and x, y, z ∈ 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.