Geometric Wire Routing
Bastert, Oliver and Fekete, Sandor P.
(1998)
Geometric Wire Routing.
Technical Report
p.
Abstract
We consider the problem of connecting n pairs of points in the plane by pairwise disjoint geometric paths (''wires''). This problem is closely related to geometric aspects of chip layout; the question of the existence of a set of pairwise disjoint connections has been studied widely. In a purely geometric setting, there always is a set of disjoint wires, so the main issue is to optimize the layout. We consider several objective functions involving the length as well as the number of bends of the wires. We present techniques for showing NPhardness of this type of geometric problem.
Actions:
Content information:
Item Type:  Paper (Technical Report) 

Citations:  4 (Google Scholar)  
Uncontrolled Keywords:  complexity geometric optimization lower bounds VLSI design 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
Deposit Information:
ZAIK Number:  zpr98332 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  16 Jan 2012 15:16 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/332 