Computational co-evolution design provides a mechanism for searching a potential solution space according to a specified fitness function. Co-evolutionary design is an approach to design problem solving in which the requirements and solutions of design evolve separately and affect each other. This paper is devoted to a new computational co-evolutionary product design approach. The undirected graph for parameters of mechanism is proposed to model the relationships among design parameters. And, the shortest path for searching a vertex in an undirected graph for parameters of mechanism is also put forward. With the help of undirected graph for parameters of mechanism, the co-evolutionary product design process is then discussed in detail, with the iterative and interleaved mapping from the function, mechanism concept, structure concept, and detailed structure. The co-evolutional design of key components of a cold heading machine is given as an example, which demonstrates that the methodology is helpful to product design.