Opened Access Single bend wiring on surfaces

Show item statistics
Export to
Author: Garrido Vizuete, María de los Angeles
Márquez Pérez, Alberto
Morgana, A.
Portillo Fernández, José Ramón
Department: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 2002
Published in: Discrete Applied Mathematics, 117 (1-3), 27-40.
Document type: Article
Abstract: The following problem of rectilinear routing is studied: given pairs of points on a surface and a set of permissible orthogonal paths joining them, whether is it possible to choose a path for each pair avoiding all intersections. We prove that if each pair has one or two possible paths to join it, then the problem is solvable in quadratic time, and otherwise it is NP-complete. From that result, we will obtain that the problem of finding a surface of minimum genus on which the wires can be laid out with only one bend is NP-hard.
Size: 199.2Kb
Format: PDF



This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)