Two near-optimum planarization algorithms are presented. The algorithms belong to a general class of algorithms known as genetic algorithms because the search procedures on which they are based are inspired on the mechanics of natural selection and natural genetics. The first algorithm is intended to generate a near-maximal planar subgraph from a given graph and also provides the routing information needed to embed the subgraph on the plane. The second planarization algorithm studied finds a near-maximum independent set of a circle graph. This algorithm may be used for finding a routing on one layer from a set of {\tiB n} two-pin nets in a channel. After small modifications, it may also be used to predict the secondary structure of ribonucleic acids. The main advantage of both algorithms is that they are easily implemented in a parallel computer.
Figure 1: Convergence of the genetic algorithm to a solution of the planarization problem. ({\bf a}) Single-row representation of the best solution at the first generation. ({\bf b}) Representation of the optimal solution found several generations later.
Figure 2: The final state for a circle graph problem evolution. Dashed chords are not considered.