It is shown that the total wire length of layouts of a balanced binary tree on a 2-dimensional grid can be reduced by 33% if one does not choose the obvious ``symmetric'' layout strategy. Furthermore it is shown that the more efficient layout strategy that is presented in this article ... more >>>

In this article we consider a basic problem in the layout of VLSI-circuits, the channel-routing problem in the knock-knee mode. We show that knock-knee channel routing with 3-terminal nets is NP-complete and thereby settling a problem that was open for more than a decade. In 1987, Sarrafzadeh showed that knock-knee ... more >>>

A bipartite graph is biplanar if the vertices can be placed on two parallel lines in the plane such that there are no edge crossings when edges are drawn as straight-line segments. We study two variants of biplanarization problems: - Two-Layer Planarization TLP: can $k$ edges be deleted from a ... more >>>