Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with graph drawing:
TR01-069 | 24th October 2001
Robert Albin Legenstein

Optimizing the Layout of a Balanced Tree

Revisions: 1

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

TR01-076 | 24th October 2001
Robert Albin Legenstein

On the Complexity of Knock-knee Channel-Routing with 3-Terminal Nets

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

TR04-078 | 3rd August 2004
Henning Fernau

Two-Layer Planarization: Improving on Parameterized Algorithmics

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

ISSN 1433-8092 | Imprint