  We consider longstanding questions concerning configuration spaces of 1-dof
tree-decomposable linkages in 2D. By employing the notion Cayley configuration
space, i.e., a set of intervals of realizable distance-values for an
independent non-edge, we answer the following. (1) How to measure the
complexity of the configuration space and efficiently compute that of low
algebraic complexity? (2) How to restrict the Cayley configuration space to be
a single interval? (3) How to efficiently obtain continuous motion paths
between realizations? (4) How to bijectively represent of the Cartesian
realization space as a curve in an ambient space of minimum dimension? (5) How
robust is the complexity measure (1) and how to efficiently classify linkages
according to it?
  In Part I of this paper, we deal with problems (1)-(4) by introducing the
notions of (a) Cayley size, the number of intervals in the Cayley configuration
space, (b) Cayley computational complexity of computing the interval endpoints,
and (c) Cayley (algebraic) complexity of describing the interval endpoints.
Specifically (i) We give an algorithm to find the interval endpoints of a
Cayley configuration spac. For graphs with low Cayley complexity, we give the
following. (ii) A natural, minimal set of local orientations, whose
specification guarantees Cayley size of 1 and $O(|V|^2)$ Cayley computational
complexity. Specifying fewer local orientations results in a superpolynomial
blow-up of both Cayley size and computational complexity, provided P is
different from NP. (iii) An algorithm--for generic linkages--to find a path of
continuous motion (provided exists) between two given realizations, in time
linear in a natural measure of path length. (iv) A canonical bijective
representation of the Cartesian realization space in minimal ambient dimension,
also for generic linkages.
