Geometric Wire Routing

Bastert, Oliver and Fekete, Sandor P. (1998) Geometric Wire Routing.
Technical Report p.


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 NP-hardness of this type of geometric problem.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr98-332
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 15:16