A direct linear-time planarity test for unflippable modules

Abstract

An easy and dirccl linear-time algorithm is provided for deciding whether there is a placement of given unflippable modules in a bounding box. such that equally labeled terminals can be connected in the plane without crossover.

Keywords:

• Graph planar embedding
• planar routing in integrated circuit layout
• river routing
• modules
• terminals

C.R. Categories:

• B.6
• G.2
• I.3

^†While this work was being carried out the author was partially supported by the Rothschild Foundation. Jerusalem.

^†While this work was being carried out the author was partially supported by the Rothschild Foundation. Jerusalem.

Notes

^†While this work was being carried out the author was partially supported by the Rothschild Foundation. Jerusalem.