On the complexity of the existence of flexible realizations

Abstract

A connected graph has a flexible realization in the plane if and only if it 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. Garamvölgyi proved that the question whether a graph has a NAC-coloring, and hence also the existence of a flexible realization, is 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+ε for every fixed ε>0. We also discuss fixed parameter tractability by treewidth and algorithms for searching NAC-colorings of a graph. This is joint work with Petr Laštovička.