Geometrische Verdrahtungsprobleme

Bastert, Oliver and Fekete, Sandor P. (1996) Geometrische Verdrahtungsprobleme.
Technical Report , 81 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 NP-hardness of this type of geometric problem. Furthermore, we prove a lower bound for the number of bends that may be necessary. Finally, we discuss approximation methods.


Actions:
Download: [img] Postscript
Download (5MB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-247
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 10:07
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/247