Hierarchical Extraction of a Spanning Planar Subgraph Maintaining Clockwise Directedness of Cycles
Daisuke Takafuji, Takao Watanabe · 2005
The subject of the paper is to propose algorithms of high capability for extracting a spanning planar subgraph G/sub p/=(V, E/sub p/) of a given graph G=(V,E) containing several directed cycles such that there is a plane embedding G/spl tilde//sub 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.