Hierarchical extraction of a spanning planar subgraph maintaining clockwise directedness of cycles

The subject of the paper is to propose algorithms of high capability for extracting a spanning planar subgraph G_p=(V, E_p) of a given graph G=(V,E) containing several directed cycles such that there is a plane embedding G˜_p in which all directed cycles are embedded as clockwise directed ones. Experimental results provided for comparison of capability show that PLAN-DIVIDE is superior to other existing ones. These algorithms have important and useful applications such as hierarchical extraction of a large spanning planar subgraph for a huge graph that cannot be handled by conventional algorithms, handling one-sided elements or modules in layout design of PWB or VLSI, and iterative improvement of layouts for PWB or VLSI.