An Animated Library of Combinatorial VLSI-Routing Algorithms

We present a library, CRoP, of combinatorial algorithms for routing problems that occur during the design process of integrated circuits. Most of them are really sophisticated theoretical algorithms, and most of them are implemented here the first time at all. The library comes with a graphical display, which is used for animating, demonstrating, and teaching combinatorial VLSI algorithms. We report good and bad experiences gained throughout the project. The main experience, which we substantiate by a brief case study, is that designing and analysing efficient algorithms is not the whole work, that implementation and integration is a research topic in its own right, and that this research may in turn have a strong influence on theory