DocumentCode
3393433
Title
A new better algorithm for rectilinear embedding of four-regular graphs
Author
Wang, Fangshi ; Xu De
Author_Institution
Dept. of Comput. Sci. & Technol., Northern Jiaotong Univ., Beijing, China
fYear
2002
fDate
6-7 Nov. 2002
Firstpage
303
Lastpage
307
Abstract
Rectilinear embedding has provided a theoretic system for the planar design of VLSI circuit. According to this system, the paper shows a new algorithm that can generate the graph example of the four-regular graph with any number of vertices, determine its bipolar orientation and bipolar numbering, draw its rectilinear embedding graph and optimize the drawing. We have compared our algorithm with those in (Tamassia and Tollis, 1989) and (Tamassia, 1987) and obtained less total number of the bends in the similar situation.
Keywords
VLSI; circuit CAD; graph theory; integrated circuit design; VLSI circuit; bipolar numbering; bipolar orientation; four-regular graphs; graph drawing; planar design; rectilinear embedding graph; Algorithm design and analysis; Capacitors; Computer science; Electronic circuits; Electronic components; Electronic equipment; Inductors; Printed circuits; Resistors; Very large scale integration;
fLanguage
English
Publisher
ieee
Conference_Titel
Autonomous Decentralized System, 2002. The 2nd International Workshop on
Print_ISBN
0-7803-7624-2
Type
conf
DOI
10.1109/IWADS.2002.1194688
Filename
1194688
Link To Document