A cycle basis in an undirected graph is a minimal set of simple cycles whose symmetric differences include all Eulerian subgraphs of the given graph. We define a rooted cycle basis to be a cycle basis in which all cycles contain a specified root edge, and we investigate the algorithmic problem of constructing rooted cycle bases. We show that a given graph has a rooted cycle basis if and only if the root edge belongs to its 2-core and the 2-core is 2-vertex-connected, and that constructing such a basis can be performed efficiently. We show that in an unweighted or positively weighted graph, it is possible to find the minimum weight rooted cycle basis in polynomial time. Additionally, we show that it is NP-complete to find a fundamental rooted cycle basis (a rooted cycle basis in which each cycle is formed by combining paths in a fixed spanning tree with a single additional edge) but that the problem can be solved by a fixed-parameter-tractable algorithm when parameterized by clique-width.

In this paper we present an algorithm that automatically creates the linkage loop equations for planar 1-DoF linkages of any topology with rotating joints, demonstrated up to 8-bars. The algorithm derives the linkage loop equations from the linkage graph by establishing a cycle basis through a single common edge. Divergent and convergent loops are identified and used to establish the fixed angles of the ternary and higher links. Results demonstrate the automated generation of the linkage loop equations for the five distinct 6-bar mechanisms, Watt I-II and Stephenson I-III, as well as the seventy one distinct 8-bar mechanisms. The resulting loop equations enable the automatic derivation of the Dixon determinant for linkage kinematic analysis of the position of every possible assembly configuration. The loop equations also enable the automatic derivation of the Jacobian for singularity evaluation and tracking of a particular assembly configuration over the desired range of input angles. The methodology provides the foundation for the automated configuration analysis of every topology and every assembly configuration of 1-DoF linkages with rotating joints up to 8-bar. The methodology also provides a foundation for automated configuration analysis of 10-bar and higher linkages.

In this paper, we present an algorithm that automatically creates the linkage loop equations for planar one degree of freedom, 1DOF, linkages of any topology with revolute joints, demonstrated up to 8 bar. The algorithm derives the linkage loop equations from the linkage adjacency graph by establishing a rooted cycle basis through a single common edge. Divergent and convergent loops are identified and used to establish the fixed angles of the ternary and higher links. Results demonstrate the automated generation of the linkage loop equations for the nine unique 6-bar linkages with ground-connected inputs that can be constructed from the five distinct 6-bar mechanisms, Watt I-II and Stephenson I-III. Results also automatically produced the loop equations for all 153 unique linkages with a ground-connected input that can be constructed from the 71 distinct 8-bar mechanisms. The resulting loop equations enable the automatic derivation of the Dixon determinant for linkage kinematic analysis of the position of every possible assembly configuration. The loop equations also enable the automatic derivation of the Jacobian for singularity evaluation and tracking of a particular assembly configuration over the desired range of input angles. The methodology provides the foundation for the automated configuration analysis of every topology and every assembly configuration of 1DOF linkages with revolute joints up to 8 bar. The methodology also provides a foundation for automated configuration analysis of 10-bar and higher linkages.