ABSTRACT
Set theory, combinatorial theory and graph theory provide the necessary mathematical foundation to place modules and route interconnects. These theories play an important role in developing algorithms to characterize electronic nets; expressing the relations between nets, the workspace, and placement constraints; and in formulating models to place modules and route electronic nets onto a workspace. Set theory describes the basic relations among collections of objects, and many concepts in mathematics and computer science can be conveniently expressed in the language of sets. This chapter introduces the definitions, expressions, and properties of sets as they relate to placement and routing methods. It also discusses the concepts of permutations and combinations, followed by two combinatorial problems which are related to routing. The first is associated with determining the number of rectilinear edges between two points with a specific number of bends. The second is concerned with finding the shortest tour for the traveling salesman problem.
