Every embedding of a dense graph has a rigid subset - Jozsef Solymosi (University of British Columbia)

While the problem of determining whether an embedding of a graph G in the plane is infinitesimally rigid is well understood, specifying whether a given embedding of G is rigid or not is still a hard task that requires ad hoc arguments.

In this talk, we show that every embedding (not necessarily generic) of a dense enough graph which satisfies that no three vertices of G are embedded to a common line, must have a subframework of size at least three which is rigid.

We do not know whether our assumption on the number of edges being $\Omega(n^{3/2}\log n)$ is tight, and we provide a construction that shows that requiring $\Omega(n\log n)$ edges is necessary.

Joint work with Orit Raz.