  We continue to study Cayley configuration spaces of 1-dof linkages in 2D
begun in Part I of this paper, i.e. the set of attainable lengths for a
non-edge. In Part II, we focus on the algebraic complexity of describing
endpoints of the intervals in the set, i.e., the Cayley complexity.
  Specifically, We focus on Cayley configuration spaces of a natural class of
1-dof linkages, called 1-dof tree-decomposable linkages. The underlying graphs
G satisfy the following: for some base non-edge f, G \cup f is
quadratic-radically solvable (QRS), meaning that G \cup f is minimally rigid,
and given lengths \bar{l} of all edges, the corresponding linkage (G \cup f,
\bar{l}) can be simply realized by ruler and compass starting from f. It is
clear that the Cayley complexity only depends on the graph G and possibly the
non-edge f. Here we ask whether the Cayley complexity depends on the choice of
a base non-edge f. We answer this question in the negative, thereby showing
that low Cayley complexity is a property of the graph G (independent of the
non-edge f).
  Then, we give a simple characterization of graphs with low Cayley complexity,
leading to an efficient algorithmic characterization, i.e. an efficient
algorithm for recognizing such graphs.
  Next, we show a surprising result that (graph) planarity is equivalent to low
Cayley complexity for a natural subclass of 1-dof triangle-decomposable graphs.
While this is a finite forbidden minor graph characterization of low Cayley
complexity, we provide counterexamples showing impossibility of such finite
forbidden minor characterizations when the above subclass is enlarged.
