Title :
Finding double Euler trails of planar graphs in linear time [CMOS VLSI circuit design]
Author :
Chen, Zhi-Zhong ; He, Xin ; Huang, Chun-Hsi
Author_Institution :
Dept. of Math. Sci., Tokyo Denki Univ., Saitama, Japan
Abstract :
The paper answers an open question in the design of complimentary metal-oxide semiconductor (CMOS) VLSI circuits. It asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding ε such that ε has a Euler trail P=e1e 2...em and its dual graph has a Euler trail P*=e 1*e2*...em* where ei* is the dual edge of ei for i=1, 2, ..., m. The paper answers this question in the affirmative by presenting a linear-time algorithm
Keywords :
CMOS integrated circuits; VLSI; circuit layout CAD; graph theory; integrated circuit layout; CMOS VLSI circuits; complimentary metal-oxide semiconductor VLSI circuit design; double Euler trails; dual edge; dual graph; linear time; linear-time algorithm; planar graphs; plane embedding; polynomial-time algorithm; Boolean functions; CMOS technology; Circuits; Helium; MOSFETs; Polynomials; Very large scale integration; Visualization;
Conference_Titel :
Foundations of Computer Science, 1999. 40th Annual Symposium on
Conference_Location :
New York City, NY
Print_ISBN :
0-7695-0409-4
DOI :
10.1109/SFFCS.1999.814603
