One of the questions in Rigidity Theory is whether a realization of the vertices of a graph in the plane is flexible, namely, if it allows a continuous deformation preserving the edge lengths. A flexible realization of a connected graph in the plane exists if and only if the graph has a NAC-coloring, which is a surjective edge coloring by two colors such that for each cycle, either all the edges have the same color, or there are at least two edges of each color. The question whether a graph has a NAC-coloring, and hence also the existence of a flexible realization, has been proven to be NP-complete. We show that this question is also NP-complete on graphs with maximum degree five and on graphs with the average degree at most $4+\varepsilon$ for every fixed $\varepsilon >0$. We also show that NAC-colorings can be counted in linear time for graphs with bounded treewidth. Since the only existing implementation of checking the existence of a NAC-coloring is rather naive, we propose new algorithms along with their implementation, which is significantly faster. We also focus on searching all NAC-colorings of a graph, since they provide useful information about its possible flexible realizations.

翻译：刚性理论中的一个核心问题是：图中顶点在平面内的实现是否具有柔性，即是否存在保持边长度不变的连续形变。连通图在平面内存在柔性实现的充要条件是该图具有NAC着色——一种使用两种颜色的满射边着色，要求每个环要么所有边颜色相同，要么至少包含两种颜色的边各两条。先前研究已证明判断图是否具有NAC着色（进而判断柔性实现是否存在）属于NP完全问题。本文进一步证明：对于最大度不超过五的图，以及对于任意固定ε>0时平均度不超过4+ε的图，该问题同样具有NP完全性。同时，我们提出对于有界树宽图，可在线性时间内计算NAC着色方案数。鉴于现有NAC着色存在性检测算法的实现较为朴素，本文设计了新算法并完成实现，其运行效率显著提升。此外，由于NAC着色能为图的可能柔性实现提供关键信息，我们还重点研究了枚举图中所有NAC着色的方法。