Euler paths in series parallel graphs

Given a series-parallel graph, we consider the problem of drawing its layout in the plane (and the planar dual of the layout) such that the euler count of the layout is minimized. This problem is of considerable importance to the design of CMOS circuits. Even though it was believed that there cannot exist a polynomial time algorithm for this problem, we have been able to design a polynomial time algorithm. The degree of the polynomial is unrealistically large. The main interest is in the existence of a polynomial time algorithm for the problem. We are not aware of any natural problem for which a natural dynamic programming based algorithm has such a large degree.

Authors

• S. Rao Kosaraju

Keywords

No keywords are indexed for this paper.