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 are unaffected by the changes in the geometric properties of the mechanisms. This work focus on the three classical problems in this area: 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. This work illustrates the successful use of techniques from graph theory and combinatorial optimization to efficiently solve these classical structural kinematic problems. A polynomial-time algorithm for degeneracy testing along with efficient algorithms to synthesize all non-isomorphic planar kinematic mechanisms are presented.