Design of mechanisms is an important branch of the theory of mechanical design. Kinematic structural studies play an important role in the design of mechanisms. These studies consider only the interconnectivity pattern of the individual links and hence, these studies are unaffected by the changes in the geometric properties of the mechanisms. The three classical problems in this area and the focus of this work are: synthesis of all non-isomorphic kinematic mechanisms; detection of all non-isomorphic pairs of mechanisms; and, classification of kinematic mechanisms based on type of mobility. Also, one of the important steps in the synthesis of kinematic mechanisms is the elimination of degenerate or rigid mechanisms. The computational complexity of these problems increases exponentially as the number of links in a mechanism increases. There is a need for efficient algorithms for solving these classical problems. This dissertation illustrates the successful use of techniques from graph theory and combinatorial optimization to solve structural kinematic problems.

An efficient algorithm is developed to synthesize all non-isomorphic planar kinematic mechanisms by adapting a McKay-type graph generation algorithm in combination with a degeneracy testing algorithm. This synthesis algorithm is about 13 times faster than the most recent synthesis algorithm reported in the literature.

There exist efficient approaches for detection of non-isomorphic mechanisms based on eigenvalues and eigenvectors of the adjacency or related matrices. However these approaches may fail to detect all cases. The reliability of these approaches is established in this work. It is shown, for the first time, that if the number of links is less than 15, the eigenvector approach detects all non-isomorphic mechanisms. A matrix is also proposed whose characteristic polynomial detects non-isomorphic mechanisms with a higher reliability than the adjacency or Laplace matrix.

An erroneous assumption often found in structural studies is that the graph of a planar kinematic chain is a planar graph. It is shown that all the existing algorithms for degeneracy testing and mobility type identification, except those by Lee and Yoon, have this error. Further, Lee and Yoon's algorithms are heuristic in nature and were not rigorously proved. Several structural results and implicit assumptions for planar kinematic chains are proved in this work without relying on the erroneous assumption. These new results provide the mathematical justification for Lee and Yoon's algorithms, thereby validating the adoption of the Lee and Yoon's algorithms for practical applications. A polynomial-time algorithm based on combinatorial optimization techniques is proposed for degeneracy testing. This polynomial-time algorithm is the first degeneracy testing algorithm that works for both planar and spatial kinematic mechanisms with different types of joints.