Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Science 15 September 1989:
Vol. 245. no. 4923, pp. 1221 - 1223
DOI: 10.1126/science.245.4923.1221
Prev | Table of Contents | Next

Articles

A Near-Optimum Parallel Planarization Algorithm

YOSHIYASU TAKEFUJI 1 and KUO-CHUN LEE 1

1 Department of Electrical Engineering, Center For Automation and Intelligent Systems Research, Case Western Reserve University, Cleveland, OH 44106.

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.

Submitted on May 30, 1989
Accepted on July 25, 1989

To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)