Title page for ETD etd-0430103-155731

Document Type	thesis
Author Name	Freeman, Andre
URN	etd-0430103-155731
Title	Dual-Eulerian Graphs with Applications to VLSI Design
Degree	MS
Department	Mathematical Sciences
Advisors	Brigitte Servatius, Advisor
Keywords	Dual Eulerian Graphs VLSI
Date of Presentation/Defense	2003-05-30
Availability	unrestricted
Abstract A Dual-Eulerian graph is a plane multigraph G that contains an edge list which is simultaneously an Euler tour in G and an Euler tour in the dual of G. Dual-Eulerian tours play an important role in optimizing CMOS layouts of Boolean functions. When circuits are represented by undirected multigraphs the layout area of the circuit can be optimized through finding the minimum number of disjoint dual trails that cover the graph. This paper presents an implementation of a polynomial time algorithm for determining whether or not a plane multigraph is Dual-Eulerian and for finding the Dual-Eulerian trail if it exists.
Files	andre.pdf

Browse by Author | Browse by Department | Search all available ETDs