Robert Albin Legenstein

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 >>>

Robert Albin Legenstein

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 >>>

Henning Fernau

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 >>>