DocumentCode :
3540965
Title :
Hierarchical extraction of a spanning planar subgraph maintaining clockwise directedness of cycles
Author :
Takafuji, Daisuke ; Watanabe, Toshimasa
Author_Institution :
Graduate Sch. of Eng., Hiroshima Univ., Japan
fYear :
2005
fDate :
23-26 May 2005
Firstpage :
172
Abstract :
The subject of the paper is to propose algorithms of high capability for extracting a spanning planar subgraph Gp=(V, Ep) 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.
Keywords :
directed graphs; integrated circuit layout; printed circuit layout; PLAN-DIVIDE; PWB layout design; VLSI layout; cycle clockwise directedness maintenance; directed cycles; one-sided elements; one-sided modules; spanning planar subgraph; subgraph hierarchical extraction; Algorithm design and analysis; Circuits; Clocks; Iterative algorithms; Maintenance engineering; Planarization; Process design; Turning; Very large scale integration; Wiring;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Circuits and Systems, 2005. ISCAS 2005. IEEE International Symposium on
Print_ISBN :
0-7803-8834-8
Type :
conf
DOI :
10.1109/ISCAS.2005.1464552
Filename :
1464552
Link To Document :
بازگشت