Graph Layout Algorithms for Automated Sketching of Linkage Mechanisms

Abstract

The graph layout problem arises frequently in the conceptual stage of mechanism design, specially in the enumeration process where hundreds of topological solutions must be analyzed. Several combinatorial, heuristic (e.g. geometrical and genetic algorithms), and force-directed algorithms (based on spring models, self-organizing maps) have been used for layout of graphs of kinematic chains and linkage mechanisms. Two main objectives of graph layout are the avoidance of edge crossings and the aesthetics. Edge crossings cannot be always avoided by force-directed algorithms since they reach a minimum of the energy in dependence with the initial position of the vertices, often randomly generated. Since the number of vertices of graphs of mechanisms is low, combinatorial algorithms can b e used to find an adequate initial position. In this paper, we present a combination of two algorithms: a combinatorial algorithm based on the exhaustive exploration of loop combinations with identification of all possible forms of drawing the graph as a base circle and successive arcs, followed by a force-directed algorithm based on spring repulsion and electrical attraction. The first algorithm is used to find an initial layout without edge crossings; then, the force-directed algorithm is used to achieve regularity on edges sizes and nodes distribution. Several available graphs of complex kinematic chains are used to validate the results. The layouts obtained have go od quality in terms of minimization of edge crossings and maximization of aesthetic characteristics.