PT - JOURNAL ARTICLE
AU - TAKEFUJI, YOSHIYASU
AU - LEE, KUO-CHUN
TI - A Near-Optimum Parallel Planarization Algorithm
AID - 10.1126/science.245.4923.1221
DP - 1989 Sep 15
TA - Science
PG - 1221--1223
VI - 245
IP - 4923
4099 - http://science.sciencemag.org/content/245/4923/1221.short
4100 - http://science.sciencemag.org/content/245/4923/1221.full
SO - Science1989 Sep 15; 245
AB - A near-optimum parallel planarization algorithm is presented. The planarization algorithm, which is designed to embed a graph on a plane, uses a large number of simple processing elements called neurons. The proposed system, composed of an N x N neural network array (where N is the number of vertices), not only generates a near-maximal planar subgraph from a nonplanar graph or a planar graph but also embeds the subgraph on a single plane within 0(1) time. The algorithm can be used in multiple-layer problems such as designing printed circuit boards and routing very-large-scale integration circuits.