DocumentCode :
3000656
Title :
Extracting nonplanar connections in a terminal-vertex graph
Author :
Miuno, Eni ; Abaashi, Toshihiro ; Watanabe, Toshio
Author_Institution :
Dept. of Circuits & Syst., Hiroshima Univ., Japan
Volume :
6
fYear :
1999
fDate :
36342
Firstpage :
121
Abstract :
This paper proposes a method for extracting a spanning planar subgraph from a given graph called a terminal-vertex graph, in which a path or a directed cycle represents how pins of a given element of electrical circuits are located, and a net performs the connection requirement among pins. It is based on transforming the graph without changing the connection requirement of each net. Experimental results are provided to show the capability of the proposed method. Finding a smallest possible set of nonplanar connections or extracting a largest planar spanning subgraph of this graph has application to the routing problem in layout design of printed wiring boards or of VLSI
Keywords :
VLSI; graph theory; integrated circuit layout; network routing; printed circuit design; VLSI; connection requirement; directed cycle; layout design; nonplanar connections; printed wiring boards; routing problem; spanning planar subgraph; terminal-vertex graph; Circuits and systems; Clocks; Joining processes; Pins; Routing; Systems engineering and theory; Very large scale integration; Wiring;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Circuits and Systems, 1999. ISCAS '99. Proceedings of the 1999 IEEE International Symposium on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7803-5471-0
Type :
conf
DOI :
10.1109/ISCAS.1999.780110
Filename :
780110
Link To Document :
بازگشت